Leecode N个数的和合集【1、15、16、18、167、454、923】
Leecode N个数的和合集【1、15、16、18、167、454、923】
两个数的和。给一个数组和目标 target，求数组中两个数的和为 target 的数的索引。
这道题用 Hash Table 求解，从左到右遍历数组，Hash Table 中存储每个数及其索引，如果再来一个数，先用 target 减去该数得到差值，然后判断差值是否在 Hash Table 中。如果在，说明差值和当前数的和等于 target，返回它们的索引即可。时间复杂度和空间复杂度均为 O(N)。
Python3 实现：
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dic = dict()
for k, v in enumerate(nums):
t = target - v
if t not in dic: # 判断差值是否在dic中
dic[v] = k
else:
return [dic[t], k]问题描述：【Sort+Two Pointers】15. 3Sum
求解思路：
三个数的和。给一个数组，找出所有满足 a+b+c=0 的结果。
因为题目要求结果不包含重复的元组，因此先要对数组升序排序。 三个数的和问题，可以把第一个数当作目标数，然后在剩余的元素中求两个数的和，求解两个数的和的方法有上面的 Leetcode 1 哈希表法和下面的 Leetcode 167 双指针法。刚开始写了个哈希表法，结果超时了，换成双指针通过了。时间复杂度为 O(N^2)，空间复杂度为 O(1)。
注意：只是升序排序还是不能完全去重，如 nums = [0,0,0,0,0]，使用双指针法仍然可能得到多个 [0,0,0]。解决方法是可以将结果以元组的形式（因为元组可哈希）存入集合 set，每次产生一个结果判断结果是否在集合 set 中，没有再加进去。
Python3 实现：
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
N = len(nums)
if N <= 2:
return []
nums.sort() # 先升序排序
ans = set() # 保存在集合去重
for i in range(N-2): # nums[i] 为第一个数
low, high = i + 1, N - 1
while low < high: # 首尾指针求两个数的和
twosum = nums[low] + nums[high]
if twosum == -nums[i]: # -nums[i]为两个数的和的target
tmp = (nums[i], nums[low], nums[high])
if tmp not in ans:
ans.add(tmp)
low += 1 # 找到一组解还要继续向内部继续搜索，如 [-5,1,2,3,4]
high -= 1
elif twosum < -nums[i]:
low += 1
else:
high -= 1
return list(ans)
print(Solution().threeSum([0,0,0,0])) # [[0,0,0]]问题描述：【Sort+Two Pointers】16. 3Sum Closest
解题思路：
这道题给一个数组和一个目标 target，求三个数的和最接近 target 的值。
做法同上面的 Leetcode 15，即先将数组升序排列，外层循环记录第一个数，使用首尾指针记录第二、第三个数。因为要找三个数的和最接近 target 的，如果等于 target 直接返回；如果不相等，那么就还需要一个变量 sub 来记录三个数的和与 target 的最小差值，每次去更新这个最小差值和对应结果，最后返回最小差值对应的结果即可。
时间复杂度为 O(N^2)，空间复杂度为 O(1)。
Python3 实现：
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
N = len(nums)
nums.sort()
ans = sub = float("inf") # ans记录结果，sub记录最小差值
for i in range(N-2):
low, high = i + 1, N - 1
while low < high:
threesum = nums[i] + nums[low] + nums[high]
if abs(threesum-target) < sub: # 更新最接近的差值和结果
ans = threesum
sub = abs(threesum-target)
if threesum == target:
return threesum
elif threesum < target:
low += 1
else:
high -= 1
return ans
print(Solution().threeSumClosest([1,2,5,10,11], 12)) # 13问题描述：【Sort+Two Pointers】18. 4Sum
解题思路：
这道题是给一个数组和 target，找到所有满足四个数的和为 target 的结果。
类似于上面的 Leetcode 15，四个数的和转化为三个数的和的问题，即先升序排序，然后前两层循环分别指向第一、第二个数，再使用首尾指针指向第三、第四个数，判断和 target 的大小关系。代码基本上和 Leetcode 15 一样。时间复杂度为 O(N^3)。
Python3 实现：
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
N = len(nums)
if N <= 3:
return []
nums.sort() # 升序排列
ans = set() # 存储在集合去重
for i in range(N - 3): # i指向第一个数
for j in range(i + 1, N - 2): # j指向第二个数
low, high = j + 1, N - 1
while low < high:
foursum = nums[i] + nums[j] + nums[low] + nums[high]
if foursum == target:
tmp = (nums[i], nums[j], nums[low], nums[high])
if tmp not in ans:
ans.add(tmp)
low += 1
high -= 1
elif foursum < target:
low += 1
else:
high -= 1
return list(ans)拓展：
- 实际上，这道题还有改进的方法，可以使用 Leetcode 1 中计算两个数的和的方法，做两次，时间复杂度可以降为 O(N^2)。
- 如果计算 N 个数的和，可以使用 DFS 回溯法求解。
问题描述：【Two Pointers】167. Two Sum II - Input array is sorted
解题思路：
这道题是给一个排序好的数组，求数组中两个数的和为 target 的数的索引。
因为数组是排好序的（升序），因此可以使用首尾指针的方法。如果首尾指针数字之和小于目标，说明首指针指向的数字太小，首指针就往后移动；如果首尾指针数字之和大于目标，说明尾指针指向的数字太大，尾指针就往前移动；如果首尾指针数字之和等于目标，返回两个数的索引即可。时间复杂度为 O(N)，空间复杂度为 O(1)。
Python3 实现：
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
low, high = 0, len(numbers) - 1
while low < high:
t = numbers[low] + numbers[high]
if t == target:
return [low + 1, high + 1]
elif t < target:
low += 1
else:
high -= 1问题描述：【Hash Table】454. 4Sum II
解题思路：
这道题是给四个数组 A、B、C、D，分别选一个数，求四个数的和为 0 的数目。
- 很明显，如果是暴力，那么时间复杂度将会是 O(N^4)，超时；
- 进一步，我们可以将数组 D 存放在字典中，键为不同的数字，值为不同数字出现的次数；然后，三层循环判断前三个数的和的负值 tmp 是否在字典中，如果在，累加 tmp 的次数，这样时间复杂度为 O(N^3)，写了一下，也超时了，pass；
- 更近一步，我们可以对四个列表两两分组，先将 A 和 B 的结果相加，存入到字典中，键为 A + B 的和，值为 A + B 的和出现的次数；然后，两层循环判断后两个数的和的负值 tmp 是否在字典中，如果在，累加 tmp 的次数，这样时间复杂度为 O(N^2)，就能 AC 了。
后两种想法类似于上面 Leetcode 1 使用哈希表法求解两个数的和的做法。
Python3 实现：
class Solution:
def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
N = len(A)
ABsum = [A[i] + B[j] for i in range(N) for j in range(N)]
ABdict = collections.Counter(ABsum) # 统计A+B的次数
ans = 0
for i in range(N):
for j in range(N):
if - (C[i] + D[j]) in ABdict: # 后两个数的和的负值在字典中能找到
ans += ABdict[- (C[i] + D[j])]
return ans更简洁的写法如下：
class Solution:
def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
N = len(A)
ABsumDict = collections.Counter([-A[i]-B[j] for i in range(N) for j in range(N)])
return sum([ABsumDict[C[i]+D[j]] for i in range(N) for j in range(N)])问题描述：【Sort+Two Pointers+Math】923. 3Sum With Multiplicity
解题思路：
这道题是给一个数组和目标 target，求满足 i < j < k and A[i] + A[j] + A[k] == target 的数目。
这道题和上面的 Leetcode 15 很类似，可以先对数组升序排序，然后使用首尾指针。但是此题的结果可能非常大，因此如果一个一个统计的话， 肯定超时。因此，还需要找到一些规律。比如，现在找到一组解 A[i] + A[j] + A[k] = target：
- 如果
A[i] == A[j] == A[k]，那么结果直接为C(count(A[i]), 3)； - 如果
A[i] == A[j] < A[k]，那么结果直接为C(count(A[i]), 2) * count(A[k])； - 如果
A[i] < A[j] == A[k]，那么结果直接为C(count(A[k]), 2) * count(A[i])； - 如果
A[i] < A[j] < A[k]，那么结果直接为count(A[i]) * count(A[j]) * count(A[k])。
其中，C(m,n) 为组合数，count(x) 为数字 x 的个数。
因此，我们还要先对数组中各个数字进行计数，然后使用排序+首尾指针的方法，用上述规律可以很快计算出结果，最后别忘了对结果取余 10 ** 9 + 7。时间复杂度为 O(N^2)。
注意：外层循环指向的第一个数以及使用首尾指针指向第二、第三个数时，每次找到一组解，要移动到下次不同的数字处，防止重复计算。
Python3 实现：
class Solution:
def threeSumMulti(self, A: List[int], target: int) -> int:
def count(i, j, k): # 计算一组解 A[i]，A[j] 和 A[k] 有多少种数目
if i < j < k:
return dic[i] * dic[j] * dic[k]
elif i == j < k:
return (dic[i] * (dic[i] - 1) // 2) * dic[k]
elif i < j == k:
return dic[i] * (dic[k] * (dic[k] - 1) // 2)
else: # i == j == k
return dic[i] * (dic[i] - 1) * (dic[k] - 2) // 6
N = len(A)
A.sort() # 升序排序
dic = collections.Counter(A) # 对各个数字计数
ans = 0
for i in range(N-2):
if i > 0 and A[i] == A[i-1]: # 移到下一个不同的数字处，防止重复计算
continue
low, high = i + 1, N - 1
while low < high:
if A[i] + A[low] + A[high] == target:
ans += count(A[i], A[low], A[high])
if A[i] == A[low]: # 移动下一个不同的数字处，防止重复计算
low += dic[A[low]] - 1
else:
low += dic[A[low]]
high -= dic[A[high]] # 移动下一个不同的数字处，防止重复计算
elif A[i] + A[low] + A[high] < target:
if A[i] == A[low]: # 移动下一个不同的数字处，防止重复计算
low += dic[A[low]] - 1
else:
low += dic[A[low]]
else:
high -= dic[A[high]] # 移动下一个不同的数字处，防止重复计算
return ans % (10 ** 9 + 7) # 对结果取余改进（分三种情况考虑）：
上述方法其实可以进一步改进。因为数组中可能有很多重复的元素，所以采取上述方法每次都要定位到下一个不同的数字，比较慢。想到能不能对不同数字进行遍历求解答案呢？答案是可以的。但是我们发现，对不同数字进行遍历，只能处理 A[i] != A[j] != A[k] 情况；而对于其他情况，我们可以单独考虑，把其他情况产生的数目累加到结果上即可。具体做法如下：
- 准备工作：使用
setA = sorted(set(A))来对数组去重并按照升序排序，使用dic = collections.Counter(A)统计不同数字的次数。 - 三个数都相同，对于 setA 中的每个数字 num，如果
dic[num] >= 3 and num * 3 == target，说明三个数都相同，我们根据上述数学规律能够得出三个数相同所产生的结果，并进行累加。 - 只有两个数相同，对于 setA 中的每个数字 num，如果
dic[num] >= 2 and target - num * 2 != num，说明只有两个数相同，我们根据上述数学规律能够得出只有两个数相同所产生的结果，并进行累加。 - 三个数都不同，对于 setA 中的每个数字 num，使其指向第一个数，使用首尾指针指向第二、第三个数，根据上述数学规律能够得出三个数都不同所产生的结果，并进行累加。
- 最后，对三种情况累加的结果取余
10 ** 9 + 7，就是答案。
这种分情况考虑的做法效率更高，实现代码如下：
class Solution:
def threeSumMulti(self, A: List[int], target: int) -> int:
setA = sorted(set(A))
dic = collections.Counter(A)
ans = 0
for num in setA: # A[i] == A[j] == A[k]
if dic[num] >= 3 and num * 3 == target:
ans += dic[num] * (dic[num] - 1) * (dic[num] - 2) // 6
for num in setA: # A[i] == A[j] < A[k] or A[i] < A[j] == A[k]
if dic[num] >= 2 and target - num * 2 != num:
ans += (dic[num] * (dic[num] - 1) // 2) * dic[target - num * 2]
for i in range(len(setA) - 2): # A[i] < A[j] < A[k]
low, high = i + 1, len(setA) - 1
while low < high:
if setA[i] + setA[low] + setA[high] == target:
ans += dic[setA[i]] * dic[setA[low]] * dic[setA[high]]
low += 1
high -= 1
elif setA[i] + setA[low] + setA[high] < target:
low += 1
else:
high -= 1
return ans % (10 ** 9 + 7)