求和问题总结
题目列表
- 2 sum
- 2 sum II - input array is sorted
- 2 sum III - data structure design
- 3 sum
- 3 sum closest
- 3 sum smaller
- 4 sum
- k sum
- k sum II
问题描述
此类题目通常情况下是给出一组 n 个数字，然后给定 target 值, 需要求出 k 个数字的 sum 为 target 的组合。此类型问题的延伸变化形式有：求 closest，求组合的个数或求组合等等。
注意事项
- 可能有重复项，注意去掉重复的组合, 除了 2 sum 的题目最好先 sort 一下，这样可以方便去掉重复的项。
- sort 方法枚举的时候注意不要重复，就像 subsets 一样。
一、2 sum 解法
1. 方法1：Brute Force(暴力)
枚举所有的 k-subset, 时间复杂度就是从 N 中选出 K 个，即为：$O(n^{k})$。
2.方法2：先 sort，再 two pointer
$O(NlogN + N) = O(NlogN)$，需要注意的是 sort 之后将会改变原来的顺序。
3.方法3： HashMap (O(n))
对于 2 sum 问题来说，其实就是对每个元素 nums[i]，在数组中找是否存在 target - nums[i]，用 HashMap 保存访问过的 value ，对每个 nums[i]，检查 HashMap 中是否有 target - nums[i]，扫完一遍就能够得到结果。属于用空间换时间的做法。
Time Complexity: O(n)
Space Complexity: O(n)
后续题目
对于 Two Sum 问题：
- 如果是要返回 Index，那么优先使用 HashMap ，因为 HashMap 不会改变原来 Array 中元素的顺序。
- 如果是返回元素的 Value， 那么可以先 Sort ，然后再使用双指针的方法来处理。
对于 Three Sum、 Three Sum Closest、 Four Sum 等问题，因为大部分都是根据 Two Sum 的双指针做法的延伸，所以都是要求返回 Value。
总结
Two Pointer(双指针)
双指针的方法有利于跳过重复元素，用来计算 Closest、Smaller 等不等于 target 的问题，此类问题优先考虑使用双指针方法。
Two Sum(Input Array is sorted)
题目描述
Array 已经 sorted。
解题思路
既然已经 sorted 那就不用再担心改变顺序，直接使用 Two Pointer 方法来做就行。
Solution 1：(Two Pointer)
class Solution(object):
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
length = len(numbers)
if length < 2:
return []
#sort to allow two-pointer algorithm and skip duplicate
numbers.sort()
start, end = 0, length - 1
while start < end:
#skip duplicate elements
if start != 0 and numbers[start] == numbers[start-1]:
start += 1
elif end != length - 1 and numbers[end] == numbers[end+1]:
end -= 1
else:
curSum = numbers[start] + numbers[end]
if curSum == target:
return [start + 1, end + 1]
elif curSum < target:
start += 1
else:
end -= 1
return []
Solution 2:(Binary Search)
class Solution(object):
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
length = len(numbers)
if length < 2:
return [0, 0]
index1 = 0
index2 = 0
for i, num in enumerate(numbers):
foundPair, index = self.search(i + 1, length - 1, numbers, target - num)
if foundPair:
index1 = i + 1
index2 = index + 1
return [index1, index2]
return [index1, index2]
def search(self, start, end, numbers, t):
while start + 1 < end:
mid = start + (end - start) / 2
if numbers[mid] == t:
return True, mid
elif numbers[mid] < t:
start = mid
else:
end = mid
if numbers[start] == t:
return True, start
if numbers[end] == t:
return True, end
return False, 0
二、3 sum 解法
Three Sum 问题可以退化为 Two Sum 问题，先取出一个数 i，然后在剩下的数组中找 sum 为 target - i 的组合就可以了。
这里需要注意的是不管采用 sort 还是 HashMap 的方法，时间复杂度其实都是 $O(n^{2})$。HashMap 的解法已经介绍过来，排序的解法如下：
排序：
只需要 sort 一遍 $O(nlogn)$，然后每次取出一个数，再使用 Two Pointer 方法寻找的复杂度为 $O(n^2)$，总的时间复杂度为：$O(nlogn + n^2) = O(n^2)$。
题目描述
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: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
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)
解题方法
这里的思想主要是，取出一个元素 i，然后再用 Two Sum 的方法求其他两个，它们的
Sum 为 target - i。
遇到题目没有思路的时候都可以考虑先 sort 一下~
注意点
- 不能有重复的 set, 所以都要将数组 sort 一下，方便在 code 中跳过重复的数。
- Two Sum 可以用 HashMap, 也可以用 Two Pointer 的方法
时间复杂度 $O(nlogn + n * n) = O(n^2)$
Solution
HashMap 的方法
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
numbers = nums
if len(numbers) < 3:
return []
numbers.sort()
results = []
for idx, num in enumerate(numbers):
if idx != 0 and num == numbers[idx-1]:
#跳过重复元素
continue
target = 0 - num
#only start with afterward elements
twoSumResults = self.twoSum(numbers[idx+1:], target)
if twoSumResults:
for comb in twoSumResults:
#index should start from idx + 1
result = [numbers[idx], numbers[comb[0] + idx + 1], numbers[comb[1] + idx +1]]
result.sort()
results.append(result)
return results
def twoSum(self, numbers, target):
# need to find all combinations now
results = []
found = False
for idx, num in enumerate(numbers):
dic[num] = idx
for idx, num in enumerate(numbers):
#跳过重复元素
if idx != 0 and num == numbers[idx-1]:
continue
t = target - num
if t in dic and dic[t] > idx:
#该元素在idx的后面
found = True
results.append([idx, dic[t]])
if not found:
return None
return results
三、3 sum closest 解法
Three Sum Closest 的解法为采取类似 Three Sum ，但是不要使用 HashMap ，使用 Sort + Two Pointer 的方法可以方便的找到 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).
解题思路
这道题和 Three Sum 类似，但是这里只需要找到一个组合并且 return 他们的 Sum，并且
不用考虑重复的问题。
所以每道题的需求和情况要分析好，并且这道题有 pass 一个 target 的变量，直接用
Three Sum 的 code 就会改变了 target 得到错误的解……而不是类似的题目就把 code 改一
改……
Solution：
class Solution(object):
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
numbers = nums
if len(numbers) < 3:
return []
numbers.sort()
result = sys.maxint
minDiff = sys.maxint
for idx, num in enumerate(numbers):
t = target - num
#only start with afterward elements
curDiff, twoSumResults = self.twoSumClosest(numbers[idx+
if minDiff > curDiff:
minDiff = curDiff
result = num + numbers[idx+1+twoSumResults[0]] + numbers[idx+
return result
def twoSumClosest(self, numbers, target):
# need to find all combinations now
index1 = None
index2 = None
#record min Difference
minDiff = sys.maxint
start, end = 0, len(numbers) - 1
while start < end:
curSum = numbers[start] + numbers[end]
curDiff = abs(curSum-target)
if curDiff < minDiff:
minDiff = curDiff
index1 = start
index2 = end
if curSum < target:
start += 1
elif curSum > target:
end -= 1
else:
break
return minDiff, [index1, index2]
四、3 sum Smaller 解法
题目描述
Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.
For example, given nums = [-2, 0, 1, 3], and target = 2.
Return 2. Because there are two triplets which sums are less than 2:
[-2, 0, 1]
[-2, 0, 3]
解题方法
sort, sort, sort,重要的事情说三遍
这一题要找三个和小于 target 的数
Thres Sum 可以用 HashMap 或者 Two-Pointer 方法 Three Sum Closest 用 Two-Pointer 方法
这一题也是用 Two-Pointer 的方法更好，对于 num i，找另外两个数的和 < target - i，如果不用 Two Pointer 的话就要 $O(n * n^2) = O(n^3)$ 如果 sort 了之后用 Two-Pointer 就可以到 $O(n^2)$
Solution
class Solution(object):
def threeSumSmaller(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
numbers = nums
if len(numbers) < 3:
return 0
numbers.sort()
result = 0
for idx, num in enumerate(numbers):
t = target - num
#only start with afterward elements
twoSumResults = self.twoSum(numbers[idx+1:], t)
result += twoSumResults
return result
def twoSum(self, numbers, target):
# need to find all combinations now
if len(numbers) < 2:
return 0
result = 0
start, end = 0, len(numbers) -1
while start < end:
while end > start and numbers[start] + numbers[end] >= target:
end -= 1
if start < end:
result += end - start
start += 1
else:
break
return result
五、4 sum 解法
Four Sum 问题退化为 Three Sum 问题，可以用两个 for 循环，内部再使用 Two Sum 问题的方法来做，总的时间复杂度为：$O(n^3)$。
题目描述
4 elements sum to target
解题方法
两个 for loop ,里面 Two Sum 的 Two Pointer 方法
将 Two Pointer 写在 for-loop 里，可以减少 function call 导致的时间
Solution
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
nums.sort()
length = len(nums)
results = []
for i in range(len(nums)-3):
if i != 0 and nums[i] == nums[i-1]:
continue
for j in range(i+1, len(nums)-2):
if j!= i+1 and nums[j] == nums[j-1]:
continue
left = j + 1
right = length - 1
while left < right:
curSum = nums[i] + nums[j] + nums[left] + nums[right]
if curSum > target:
right -= 1
elif curSum < target:
left += 1
else:
results.append([nums[i], nums[j], nums[left], nums[right]])
left += 1
right -= 1
while(left < right and nums[left] == nums[left-1]:
left += 1
while(left < right and nums[right] == nums[right+1]:
right -= 1
return results
六、K sum 解法
K Sum 问题也可以一步步退化，最终变为 Two Sum 问题，K Sum 问题的时间复杂度为：$O(n^{k-1})$。
引用
非常详细，有各个题目的各种情况分析。
