java - 为什么在用hashmap解Leetcode Two Sum的时候先查解再做map.put会失败？

Question

对于经典的 Leetcode TwoSum 问题: 给定一个整数数组，返回两个数字的索引，使它们加起来达到特定目标。

您可以假设每个输入只有一个解决方案，并且您可能不会两次使用相同的元素。

例子:

给定 nums = [2, 7, 11, 15]，target = 9，因为 nums[0] + nums[1] = 2 + 7 = 9，返回 [0, 1]。

试过下面的代码，它会通过测试用例，但提交失败。

public class Solution {
    public int[] twoSum (int[] arr, int target) {
        if (arr == null || arr.length < 1) {
            throw new IllegalArgumentException ("array given is null or 
length less than 1, no two sum solutions"); 
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>(); 
        for (int i = 0; i < arr.length; i++) {
            map.put (arr[i], i);
            int component = target -arr[i]; 
            if (map.containsKey(component) && map.get(component) != i) {
                return new int[] {i, map.get(component)};
            }
        }   
        throw new IllegalArgumentException (" no two sum solution found 
"); 
    }
}

虽然如果我在解决方案检查后移动 map.put 如下，将通过，但无法弄清楚为什么？

public class Solution {
    public int[] twoSum (int[] arr, int target) {
        if (arr == null || arr.length < 1) {
            throw new IllegalArgumentException ("array given is null or 
length less than 1, no two sum solutions"); 
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>(); 
        for (int i = 0; i < arr.length; i++) {

            int component = target -arr[i]; 
            if (map.containsKey(component) && map.get(component) != i) {
                return new int[] {i, map.get(component)};
            }
            map.put (arr[i], i);
        }   
        throw new IllegalArgumentException (" no two sum solution found 
"); 
    }
}

Answer 1

如果数组包含重复项，并且 target 是两个相等数组元素的总和，您的第一个代码段将失败。

假设 target == arr[i] + arr[j] 对于一些 i 和 j 使得 i<j 和 arr[i]==arr[j]。在这种情况下，您将首先放入 map.put (arr[i], i)，然后用 map.put (arr[j], j) 覆盖它。结果，map.containsKey(component) 将为 true 但 map.get(component) != i 将为 false ，你将无法返回索引对 i 和 j。

因此，您应该在检查条件后才将当前元素添加到Map。

例如，以下输入将在第一个解决方案中失败并在第二个解决方案中成功:

twoSum(new int[] {4,5,7,5},10)