K Sum

Two Sum 系列

1.Two Sum

从一个Array中选两个数之和等于Target

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.

• 解法1. 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 ?
  • 排序后失去了indices，所以这里用排序会失掉信息
  • 返回的是值而不是indices就可以

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]
  

3 Sum 系列

15. 3Sum

从一个Array中选出三个数之和等于Target

• 结果不止一组
• 有重复的数字
• 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 add following 2 lines =.=
                    l += 1
                    r -= 1
        return res

16. 3Sum Closest

从Array中选取三个和和target最接近的值

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]
                # 只是加个这个比较而已，其他都没变
                if abs(s - target) < abs(res - target):
                    res = s
                if s > target:
                    r -= 1
                elif s < target:
                    l += 1
                else:
                    return target
        return res

18. 4Sum

class Solution(object):
    def fourSum(self, nums, target):
        def findNsum(nums, target, N, result, results):
            if len(nums) < N or N < 2 or target < nums[0]*N or target > nums[-1]*N:  # early termination
                return
            if N == 2: # two pointers solve sorted 2-sum problem
                l, r = 0, len(nums)-1
                while l < r:
                    s = nums[l] + nums[r]
                    if s == target:
                        results.append(result + [nums[l], nums[r]])
                        l += 1
                        r -= 1
                        while l < r and nums[l] == nums[l-1]:
                            l += 1
                        while l < r and nums[r] == nums[r+1]:
                            r -= 1
                    elif s < target:
                        l += 1
                    else:
                        r -= 1
            else: # recursively reduce N
                for i in range(len(nums)-N+1):
                    if i == 0 or (i > 0 and nums[i-1] != nums[i]):
                        findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)

        results = []
        findNsum(sorted(nums), target, 4, [], results)
        return results