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)（忽略常数）；第二种做
评论0