共计 2439 个字符，预计需要花费 7 分钟才能阅读完成。
点击 这里 能够查看更多算法面试相干内容~
题目形容
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。
你能够假如每种输出只会对应一个答案。然而，数组中同一个元素不能应用两遍。
你能够按任意程序返回答案。
示例 1：
输出：nums = [2,7,11,15], target = 9 输入：[0,1]
解释：因为 nums[0] + nums[1] == 9，返回 [0, 1]。
示例 2：
输出：nums = [3,2,4], target = 6
输入：[1,2]
示例 3：
输出：nums = [3,3], target = 6
输入：[0,1]
提醒：
2 <= nums.length <= 103-109 <= nums[i] <= 109-109 <= target <= 109- 只会存在一个无效答案
奢侈解法
因为咱们每次要从数组中找两个数。
因而一个很简略的思路是：应用两重循环枚举下标 i 和 j，别离代表要找的两个数。
而后判断 nums[i] + nums[j] == target 是否成立。
另外为了避免失去反复的解，咱们须要在第一层循环中让 i 从 0 开始，到 n – 2 完结（确保能取到下一位数作为 j）；在第二层循环中让 j 从 i + 1 开始，到 n – 1 完结。
class Solution {public int[] twoSum(int[] nums, int t) {
int n = nums.length;
for (int i = 0; i < n - 1; i++) {for (int j = i + 1; j < n; j++) {if (t == nums[i] + nums[j]) return new int[]{i,j};
}
}
return new int[]{};
}
}工夫复杂度：两重循环，以复杂度是 $O(n^2)$
空间复杂度：$O(1)$
哈希表解法
首先，任何优化的思路都不外乎「缩小反复」。
从奢侈解法中能够晓得，逻辑上咱们是先定下来一个数，而后从数组中往后找另外一个值是否存在。但其实咱们在找第二个数的过程中是反复扫描了数组屡次。
举个例子，对于 nums = [2,3,8,4], target = 9 的样例，咱们先确定下来第一个数是 2，而后从后扫描到最初一个数，查看是否有 7。发现没有，再决策第一个数为 3 的状况，这时候咱们应该利用前一次扫描的后果来帮忙咱们疾速判断是否存在 6，而不是再从新进行一次扫描。
这是直观的优化思路，不难想到能够应用哈希表进行存储。以数值为 key，数值的下标为 value。
当入手将想法转化为代码时，会发现如果先敲定第一个数，将前面的数退出哈希表，再进行下一位的遍历的时候，还须要将该数值从哈希表中进行删除。
class Solution {public int[] twoSum(int[] nums, int t) {Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) map.put(nums[i], i);
for (int i = 0; i < nums.length; i++) {int a = nums[i], b = t - a;
if (map.get(a) == i) map.remove(a);
if (map.containsKey(b)) return new int[]{i, map.get(b)};
}
return new int[]{};
}
}最坏状况下，每个数会对应一次哈希表的插入和删除。该解法实质是在循环过程中敲定第一个数，在哈希表中找该数前面是否存在第二个数。
这时候无妨将思路转换过去，遍历过程中敲定第二个数，应用哈希表在第二个数的后面去找第一个数。
具体的做法是，边遍历边存入哈希表，遍历过程中应用的下标 i 用作敲定第二个数，再从现有的哈希表中去找另外一个指标数（因为下标 i 后面的数都被退出哈希表了，即在下标 i 后面去找第一个数）。
class Solution {public int[] twoSum(int[] nums, int t) {Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {int a = nums[i], b = t - a;
if (map.containsKey(b)) return new int[]{map.get(b), i};
map.put(a, i);
}
return new int[]{};
}
}从 LeetCode 上的执行工夫来看，第一种哈希表做法是 4ms，而第二种哈希表的做法是 0ms（有余 1ms 的意思），快在了咱们缩小了哈希表的插入和删除操作。
但这只是常数级别上的优化，LeetCode 上的执行工夫倡议只作一般参考，还是要从算法的时空复杂度来剖析快慢。
工夫复杂度：第一种哈希表的做法会扫描数组两次，复杂度是 $O(n)$（疏忽常数）；第二种做法只会对数组进行一遍扫描，复杂度是 $O(n)$
空间复杂度：两种做法都应用了哈希表进行记录，复杂度是 $O(n)$
总结
能够看到，我将原题目的入参 target 替换成了 t，但并不影响正确性，目标是为了进步编码速度。如果你也常常参加 LeetCode 周赛，就会发现这是一个罕用的小技巧。
这个技巧，我心愿你在第一题就把握。
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.1 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先将所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
因为 LeetCode 的题目随着周赛 & 双周赛一直减少，为了不便咱们统计进度，咱们将依照系列起始时的总题数作为分母，实现的题目作为分子，进行进度计算。以后进度为 1/1916。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：Github 地址 & Gitee 地址。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其余的优选题解。
算法与数据结构
LeetCode 题解
算法面试
