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 nums[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 a `O(n)`

time.

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

You may write code in this way.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
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 ask 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 `in`

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
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 `O(n`

. ^{2})

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
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`

.^{2})

`O(n`

.^{2})

## Four Sum

Similar to the problem three `O(n`

.^{3})

Is there any more optimal ways? Hashmap.

- define a hashmap whose key=a+b and value=(a, b)
- use two
`for`

to traverse all c and d.

The time complexity is `O(n`

.^{2logn})