Find Numbers of a Sum

2Sum

From Leetcode 1. Two Sum:

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.

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

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

Naive approach: iterate all possible combinations O(n^2).

nums = [2, 7, 11, 15]
Generate =>
(2,7), (2,11), (2,15)
(7,11), (7,15)
(11,15)

We are looking for a linear method O(n).

Build a hash table:
hs = {
     7: 0,  # if it's 7, it can match the item at index 0
     2: 1,  # if it's 2, it can match the item at index 1
    -2: 2,  # if it's -2, it can match the item at index 2
    -6: 3   # if it's -6, it can match the item at index 3
}

for i, num in enumerate(nums):
    if num in hs and i != hs[num]:
        return [min(hs[num],i), max(hs[num],i)]
return None # or, raise ValueError("Not Found!")

Note: i != hs[num] prevents self-combinations.

However, the above algorithm still uses two scans, one for building the hashtable and one for searching.

Can we just use a single scan?

A: we build the hashtable along the search.

3Sum

From Leetcode 15. 3Sum:

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is: [

[-1, 0, 1],

[-1, -1, 2]

]

Naive approach: iterate all combinations O(n^3).

Can we use our previous method twoSum()?

At an element a[i], we check whether or not twoSum(nums,-a[i]) exist. However, we need to skip the index i. The accepted solution O(n^2) is given as follows:

The above method is NOT elegant. We can find a better solution.

There is a smart two-pointer solution O(n^2).

[-1,0,1,2,-1,-4]
sort: [-4,-1,-1,0,1,2]
        |  |        |
        a  b ->  <- c

a+b+c < 0: b move right
a+b+c > 0: c move left
a+b+c = 0: found, move both b and c
stop condition: b >= c

The complete code is given as follows:

The Two-Pointer idea can be used to solve 16. 3Sum Closest:

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

4Sum

We can use 3Sum (adding a target argument) to solve this problem.

def fourSum(self, nums, target):
    nums.sort()
    found = set()
    for i, num in enumerate(nums):
        for l in self.threeSum(nums[i+1:], target-num):
            found.add(tuple([num] + l))
    return list(found)