K 数之和总结
1. Two Sum
题目： https://leetcode-cn.com/problems/two-sum/description/
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例:
`给定 nums = [2, 7, 11, 15], target = 9` `因为 nums[0] + nums[1] = 2 + 7 = 9``所以返回 [0, 1]`
Solution 1
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
n = len(nums)
for x in range(n):
b = target-nums[x]
if b in nums:
y = nums.index(b)
if y!=x:
return x,y
分析：时间复杂度：O(n2)，空间复杂度：O(1) （补充：python中list对象的存储结构采用的是线性表，因此其查询复杂度为O(n) 也就是 if b in nums 时间复杂度是O(n)）。
Solution 2
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
n = len(nums)
# Create a empty dict
d = {}
for x in range(n):
a = target-nums[x]
if nums[x] in d:
return d[nums[x]],x
else:
d[a] = x
分析：时间复杂度：O(1) 、空间复杂度O(n) （补充：dict对象的存储结构采用的是散列表(hash表)，其在最优情况下查询复杂度为O(1)）。
2. Three Sum
题目：
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
思路:
首先从大的方面来看，排序之后比较容易做到去重，相同元素直接选取代表即可。
拍完序之后，以下标i从左往右遍历作为主循环，找到剩下两个加起来和为-nums[i]的两个元素。
这样的两个元素一定出现在nums[i]后面，这个限制非常关键。因为主循环是从左往右遍历，如果不限制只在当前元素后面找，则会重复答案。
加上这个限制，如果当前元素大于0，则表示后面的所有元素都大于0，三个数相加之和不可能为0.
这里有两次去重的概念，首先是在外层，如果nums[i]和上一个元素nums[i-1]相同，则直接跳过，因为相同值已经考虑过了。
另一个是在三数之和为0时，还要其他的解，这里也考虑一次去重即可。
Solution 1
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if len(nums) < 3 or nums == None:
return None
# 本题需要去重
nums.sort() # 原地排序
res = []
# 三指针： nums[j] + nums[k] == -nums[i]
for i in range(len(nums)):
# 排序之后，nums[i]大于0则不可能从后面找到解
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i - 1]:
continue
j = i + 1
k = len(nums) - 1
while j < k:
_sum = nums[i] + nums[j] + nums[k]
if _sum == 0:
temp = [nums[i], nums[j], nums[k]]
res.append(temp)
while j < k and nums[j] == nums[j + 1]:
j += 1
while j < k and nums[k] == nums[k-1]:
k -= 1
j += 1
k -= 1
elif _sum > 0:
k -= 1
elif _sum < 0:
j += 1
return res
Solution 2
class Solution(object):
def threeSum(self, nums):
'''这题跟11盛水一样，用双指针法'''
nums=sorted(nums,reverse=False) #从小到大sorted临时排序 sort永久性排序[-4 -1…2]
new_list = []
for key,value in enumerate(nums): #运用双指针时这种方法学一下
j,k = key + 1, len(nums) - 1 #从下一位和最后一位向中间遍历
while j < k: #两个指针向中间移动
if nums[j] + nums[k] + value == 0:
if [nums[j],nums[k],value] not in new_list: #去重
new_list.append([nums[j],nums[k],value])
while j < k and nums[j] == nums[j+1]: #去重
j += 1
while j < k and nums[k] == nums[k-1]: #去重
k -= 1
j += 1
k -= 1
# 大于 0, 右指针向中间移动
elif nums[j] + nums[k] + value > 0:
k -= 1
# 小于 0,左指针向中间移动
else:
j += 1
return new_list
Solution 3
class Solution:#递归解法
def threeSum(self, nums):#nums = [-1, 0, 1, 2, -1, -4]
def findNsum(nums, target, N, result, results):#result某一次结果results最终结果
if len(nums) < N or N < 2 or target < nums[0]*N or target > nums[-1]*N:#
return #某些情况：不符合N数之和；N=1；
#找不到的两种情况：target<N个最小数；target>N个最大数
if N == 2: # N数之和都要递归到两数之和解决
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
while l < r and nums[l] == nums[l-1]:#相同的数跳过
l += 1
elif s < target:
l += 1 #比target小左指针加1
else:
r -= 1 #比target大左指针加1
else: # 3数，4数，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), 0, 3, [], results)
return results
3. Four Sum
题目:
给定一个包含n个整数的数组nums和一个目标值target，判断nums中是否存在四个元素a，b，c 和d ，使得a + b + c + d的值与target相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例：
给定数组nums = [1, 0, -1, 0, -2, 2]，和target = 0。
满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/4sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路:
本题是三数之和的延续。也包含去重，所以，排序是基本操作。
三数之和是固定一个数，然后在后面用双指针查找，四数之和是固定两个数，然后用双指针在后面查找。
Solution 1
class Solution:#递归解法
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
while l < r and nums[l] == nums[l-1]:
l += 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
Solution 2
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
if len(nums) < 4 or nums == None:
return None
nums.sort()
res = []
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i-1]:
continue
newTarget = target - nums[i]
for j in range(i + 1, len(nums)):
if j > i + 1 and nums[j] == nums[j-1]:
continue
newTarget2 = newTarget - nums[j]
m = j + 1
n = len(nums) - 1
while m < n:
if nums[m] + nums[n] == newTarget2:
temp = [nums[i], nums[j], nums[m], nums[n]]
res.append(temp)
while m < n and nums[m] == nums[m+1]:
m += 1
while m < n and nums[n] == nums[n-1]:
n -= 1
m += 1
n -= 1
elif nums[m] + nums[n] > newTarget2:
n -= 1
elif nums[m] + nums[n] < newTarget2:
m += 1
return res
4. K Sum
Problem:
Given n distinct positive integers, integer k (k <= n) and a number target.
Find k numbers where sum is target. Calculate how many solutions there are?
Example:
Given [1,2,3,4], k = 2, target = 5.
There are 2 solutions: [1,4] and [2,3].
Return 2.
Note:
这道题和Distinct Subsequence很像。
使用三维动规数组dp[i][j][t]，表示从0遍历到A[i]后找到的j个元素之和为t的情况的总数。最后返回从整个A数组找到的k个元素之和为target的情况总数即可。操作如下：
首先，若第i个元素，也就是A[i-1]，大于t，那么“从前i个元素中取j个元素令j个元素之和为t的所有情况”和第i个元素无关。也就是说dp[i][j][t] = dp[i-1][j][t]。而如果最后一个元素A[i-1] <= t，那么这个元素一定能带来一些不同的“从前i个元素中取j个元素令j个元素之和为t的情况”，但是，还要加上完全不考虑这个元素A[i-1]时的解的集合，也就是dp[i-1][j-1][t-A[i-1]]。因为，加上这个元素之后的dp[i][j-1][t-A[i-1]]不会影响已经遍历过的dp[i-1][j-1][t-A[i-1]]。
[HTML_REMOVED]Solution:[HTML_REMOVED]
public class Solution {
public int kSum(int A[], int k, int target) {
int[][][] dp = new int[A.length+1][k+1][target+1];
for (int i = 0; i <= A.length; i++) dp[i][0][0] = 1;
//Super DP
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= k && j <= i; j++) {
for (int t = 1; t <= target; t++) {
dp[i][j][t] = dp[i-1][j][t];
if (A[i-1] <= t) dp[i][j][t] += dp[i-1][j-1][t-A[i-1]];
}
}
}
return dp[A.length][k][target];
}
}
