K Sum

Catalogue

1. 1. 2 Sum
   1. 1.1. 167. Two Sum II - Input array is sorted
   2. 1.2. 170. Two Sum III - Data structure design
   3. 1.3. 653. Two Sum IV - Input is a BST
2. 2. 3 Sum
   1. 2.1. 15. 3Sum
   2. 2.2. 16. 3Sum Closest
3. 3. 4 Sum

• Assumption

1. unsorted or sorted
2. return index ? or value ?
3. duplicate ?
4. size, data type, data range ?
5. optimize time or space ?
6. How many time are we going to call this function?

2 Sum

$O(n^2)$

###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, and you may not use the same element twice.

• HashTable

  # Time : O(n), Space : O(n)
  class Solution(object):
      def twoSum(self, nums, target):
          coml = {}
          for i in xrange(len(nums)):
              c = target-nums[i]
              if c in coml:
                  return [coml[c], i]
              coml[nums[i]] = i

• Why not Sort + Two Pointers ?
  • after sort, lost the information of indices
  • return indice instead of values

167. Two Sum II - Input array is sorted

• Not Zero-Based Index

  class Solution(object):
      def twoSum(self, nums, target):
          l = 0
          r = len(nums) - 1
          while l < r:
              s = nums[l] + nums[r]
              if s > target:
                  r -= 1
              elif s < target:
                  l += 1
              else:
                  return [l+1, r+1]

170. Two Sum III - Data structure design

1. HashTable, consider duplicates
2. Trade Off, quick add or quick find ?

class TwoSum(object):

    def __init__(self):
        self.nums = collections.defaultdict(int)

    def add(self, number):
        self.nums[number] += 1

    def find(self, value):
        for num in self.nums.keys():
            if value - num in self.nums and (value - num != num or self.nums[num] > 1):
                return True
        return False

653. Two Sum IV - Input is a BST

• This is a general idea for binary tree instead of BST!!!

class Solution(object):
    def findTarget(self, root, k):
        self.visited = set()
        return self.dfs(root, k)

    def dfs(self, root, k):
        if not root:
            return False

        if self.dfs(root.left, k):
            return True

        if k - root.val in self.visited:
            return True
        self.visited.add(root.val)

        if self.dfs(root.right, k):
            return True

        return False

3 Sum

$O(n^3)$

15. 3Sum

• only one results ? no
• duplicates ? yes
• The solution set must not contain duplicate triplets.

class Solution(object):
    def threeSum(self, nums):
        nums.sort()
        res = []
        for i in xrange(len(nums)-2):
            # Skip Duplicate nums at 1st place
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l = i + 1
            r = len(nums)-1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s > 0:
                    r -= 1
                elif s < 0:
                    l += 1
                else:
                    res.append([nums[i], nums[l], nums[r]])
                    # Remove Dupilcate Results
                    while l < r and nums[l] == nums[l+1]:
                        l += 1
                    while l < r and nums[r] == nums[r-1]:
                        r -= 1
                    # Forget to add following 2 lines =.=
                    l += 1
                    r -= 1
        return res

16. 3Sum Closest

class Solution(object):
    def threeSumClosest(self, nums, target):
        res = float('inf')
        nums.sort()
        for i in xrange(len(nums)-2):
            l = i + 1
            r = len(nums) - 1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                # only append this line
                if abs(s - target) < abs(res - target):
                    res = s
                if s > target:
                    r -= 1
                elif s < target:
                    l += 1
                else:
                    return target
        return res

4 Sum

$O(n^4)$