K Sum Problem

K sum problems are the sort of problems that asking you to find the k numbers whose sum is the target when given a number array or list. On LeetCode, there are two sum and three sum problems. Today, I am gonna discuss such kind of problems. 

Two Sum

Given nums = [2, 7, 11, 15],
target = 9,
Because num[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
---- https://leetcode.com/problems/two-sum/

Easily, we can think of two simple and direct solutions. One is to try all possible combinations. Another one is to use two pointers beginning at the head and the tail of the sorted list to traverse the list in an O(n)  time. 

Obviously, nobody wants the first solution to happen. So let us focus on the second one. 

You may write code in this way. 

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        sorted_nums = sorted(nums)

        l, r = 0, len(sorted_nums) - 1
        while l < r:
            s = sorted_nums[l] + sorted_nums[r]
            if s < target:
                l += 1
            elif s > target:
                r -= 1
            else:
                return l, r

Unfortunately, you will find you got WA on LeetCode. The reason is this problem asks you to return the index of the numbers in the original array. So you may find another method so as to get rid of using sorting. That should be in .

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        res = list()
        tmp_dict = dict()

        for i in range(len(nums)):
            if target - nums[i] in nums:
                j = nums.index(target - nums[i])
                if i != j:
                    return i, j

Actually, in  in Python is a O(n) time complexity operation. Though this code works, it may not be the best one. Other thoughts can be considering save the original list or use dict as a hash map, which can be regarded as a tradeoff between time-consuming and space-consuming to keep the time complexity as O(n²) . 

Three Sum

With one more element enrolled, what we can do here is to traverse all elements, and then find the other two elements with a similar method in problem two sum. 

class Solution:
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = list()
        nums.sort()

        for i in range(len(nums) - 2):
            if i > 0 and nums[i-1] == nums[i]:
                continue
            l, r = i + 1, len(nums) - 1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s < 0:
                    l += 1
                elif s > 0:
                    r -= 1
                else:
                    res.append([nums[i], nums[l], nums[r]])
                    while l < r and nums[l] == nums[l+1]:
                        l += 1
                    while l < r and nums[r] == nums[r-1]:
                        r -= 1
                    l += 1
                    r -= 1
        return res

The time complexity is O(n²) .

Actually we can still use hash map here to ensure the complexity as O(n²).

Four Sum

Similar to the problem three sum, we can fix two elements and find the other two elements with the method we use in two sum. In this way, the time complexity is O(n³) .

Are there any more optimal ways? Hashmap. 

1. define a hashmap whose key=a+b and value=(a, b)
2. use two for  to traverse all c and d. 

The time complexity is O(n^2logn).