为什么在使用HashMap求解Leetcode Two Sum时，如果在检查解决方案之前使用do Map.Put会失败？

Question

对于经典的Leetcode二和问题：给定一个数组，返回两个数的索引，使它们相加为一个特定的目标。

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

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 
"); 
    }
}

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是两个相等数组元素的和，则您的第一个代码段将失败。

假设对某些i和j目标==arr[i]+arr[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)