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

Question

I am trying to solve:

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].

Here is my solution:

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]] 

Now the solution is not correct as it fails the test case like [3,3], 6. Now both 3s get stored in hash table as one entry which is expected, so only one index is recorded in the hash table for 3 and my solution doesn't work.

So, I think the solution might not be with hash tables. But the correct solution is:

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

Now, this is essentially the same solution in Java and it is mentioned as the correct one.

So, my question is:

1. How can I change my solution in Python to work and not fail the test case?
2. How is the Java solution different, does its hash table have some other behavior?

Thanks for your help.

Answer 1

The Java solution has a check that takes care of two equal elements:

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

The first part of this condition - map.containsKey(complement) - means that the number complement is present in the Map, while the second part - map.get(complement) != i) - means that the index of complement stored in the map is different from the index i. This means that if complement == nums[i], there are two identical numbers in the input array.

I don't know Python, but it looks like your code fails because

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

always returns false when k-x == x. You need to compare hash_table[k-x] to the current index of the input array.

Based on your first Python loop, I'm assuming the second loop should look like this:

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