java - 查找数组中两个数字的总和是否等于 k

Question

我正在尝试解决:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

这是我的解决方案:

def twoSum(nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """

        hash_table = {}
        k = target

        for i, x in enumerate(nums):
            if x not in hash_table:
                hash_table[x] = i

        for x in nums:
            if k-x in hash_table:
                if hash_table[k-x]!= hash_table[x]:
                    return [hash_table[x], hash_table[k-x]] 

现在解决方案不正确，因为它没有通过 [3,3]、6 这样的测试用例。现在两个 3 都作为预期的一个条目存储在哈希表中，因此哈希表中只记录了一个索引3 而我的解决方案不起作用。

所以，我认为解决方案可能不是哈希表。但正确的解决方案是:

public int[] twoSum(int[] nums, int target) {
    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 complement = target - nums[i];
        if (map.containsKey(complement) && map.get(complement) != i) {
            return new int[] { i, map.get(complement) };
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

现在，这在 Java 中基本上是相同的解决方案，并且它被称为正确的解决方案。

所以，我的问题是:

1. 如何更改我的 Python 解决方案以使其正常工作而不会使测试用例失败？
2. Java 解决方案有何不同，它的哈希表是否有一些其他行为？

感谢您的帮助。

Answer 1

Java 解决方案有一个检查处理两个相等的元素:

if (map.containsKey(complement) && map.get(complement) != i)

此条件的第一部分 - map.containsKey(complement) - 表示数字 complement存在于 Map 中, 而第二部分 - map.get(complement) != i) - 表示 complement 的索引存储在 map 中的不同于索引 i .这意味着如果 complement == nums[i] ，输入数组中有两个相同的数字。

我不懂 Python，但看起来你的代码失败了，因为

if hash_table[k-x]!= hash_table[x]

总是在 k-x == x 时返回 false .你需要比较hash_table[k-x]到输入数组的当前索引。

根据您的第一个 Python 循环，我假设第二个循环应该如下所示:

    for i, x in enumerate(nums):
        if k-x in hash_table:
            if hash_table[k-x]!= i:
                return [i, hash_table[k-x]]