查找数组中两个数字的总和是否等于 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 都作为预期的一个条目存储在散列 table 中，因此只有一个索引记录在散列 table 中 3，我的解决方案不起作用。

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

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 中的解决方案基本相同，并且被称为正确的解决方案。

那么，我的问题是：

如何更改 Python 中的解决方案以使其正常工作而不使测试用例失败？
Java 解决方案有何不同，它的散列 table 是否有一些其他行为？

感谢您的帮助。

Answer 1

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

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

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

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

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

在 k-x == x 时始终 returns 为假。您需要将 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]]

Answer 2

为什么不选择一些简单的东西：

def twoSum(nums, target):
    for i, num1 in enumerate(nums):
        for j, num2 in enumerate(nums):
            if num1 + num2 == target and i != j:
                return [i, j]
    return [-1, -1] # or whaterver you want to say "no solution found"

这会产生：

print twoSum([2, 7, 11, 15], 9)   # =>[0, 1] 2+7
print twoSum([2, 7, 11, 15], 22)  # =>[1, 3] 7+15
print twoSum([2, 7, 11, 15], 23)  # => [-1, -1]  no solution

Answer 3

除了哈希 table 解决方案，您还可以

对数组进行排序（时间O(N Log N)），
维护两个索引 i、j 使得 num[i] + num[j] <= sum < num[i] + num[j+1]；每次增加 i 时，都会将 j 减少 0 或更多以进行调整。 i从0开始，j结束。

更糟糕的是，您增加 i N 次并减少 j N 次，总共 O(N) 次操作。如果相等，你就完成了。

这可以做到in-place。

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

Find if sum of two numbers in an array is equal to k

python

java

algorithm

hashtable

hashmap