Java-Leetcode二和哈希映射解决方案

Question

我是Java新手，刚开始做Leetcode-Two Sum。我发现除了暴力解决方案外，常见的解决方案是使用Hashmap。但我仍然无法得到它。例如，这符合我的逻辑：

public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
int[] res = new int[2];
for (int i = 0; i < nums.length; ++i) {
m.put(nums[i], i);
}
for (int i = 0; i < nums.length; ++i) {
int t = target - nums[i];
if (m.containsKey(t) && m.get(t) != i) {
res[0] = i;
res[1] = m.get(t);
break;
}
}
return res;
}

第一个for循环将数字放入Hashmap，并使用第二个for循环检查是否可以找到等于target number - nums[i]的数字。然而，我看到了许多公认的解决方案将两种for循环结合在一起，比如这个例子：

public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
int[] res = new int[2];
for (int i = 0; i < nums.length; ++i) {
if (m.containsKey(target - nums[i])) {
res[0] = i;
res[1] = m.get(target - nums[i]);
break;
}
m.put(nums[i], i);
}
return res;
}

在我的逻辑中，第二个解决方案像这样运行for循环：

//[2,7,11,15]
when i=0, m.put(nums[0],2)
when i=1, m.put(nums[1],7)
when i=2, m.put(nums[2],11)
when i=3, m.put(nums[3],15)

因为i < nums.length，所以当i=4时，代码将跳转到return res。它不会再运行for循环。但据我所知，我看到人们说第二个解决方案将遍历数组，并将索引和值存储到Hashmap中，然后再次迭代。在我的想象中，只有一个for循环，他们怎么能用唯一的for循环来再次迭代呢？

Answer 1

不会有任何第二次迭代。在一次迭代中，如果找到一对，循环就会中断。

考虑一下：

//[2,7,11,15] and target = 13
when i=0, m.put(mums[0],2)
when i=1, m.put(mums[1],7)
when i=2, m.contains(13 - mums[2]) == true // since 13 - 11 = 2 is present at index 0
res[0] = 2
res[1] = 0
break;

因此。。。。。你是对的。只有一次迭代。

Answer 2

不需要两个for循环，这可以在您发布的单个for循环中完成。从性能的角度来看，最好在for循环中只迭代一次，并在找到第一个匹配对时从循环中中断。在最坏的情况下，这是O(n(。

public static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
int rem = target - num;
if (map.containsKey(rem)) {
return new int[] { num, rem };
}
map.put(num, num);
} // for
return null;
}