轻松拿下两数、三数、四数和N数之和 | 必备算法
轻松拿下两数、三数、四数和N数之和 | 必备算法
程序员荒生
发布于 2022-03-04 11:43:56
发布于 2022-03-04 11:43:56
两数之和
题目
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：
2 <= nums.length <= 103
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案
解题
本题可以通过三种方式去解答
暴力枚举
- 最容易想到的方法是双层遍历枚举
nums，查询nums[i] + nums[j] = target
算法源码：
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
# 1. 暴力
for i in range(len(nums) - 1):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []
时间复杂度：O(N^2)，其中N是数组中的元素数量。最坏情况下数组中所有数都需要被匹配
空间复杂度：O(1)
排序 + 双指针
- 查询
nums[i] + nums[j] = target还很容易想到双指针，但双指针前提需要有序数组，故先对数组进行排序并且保留原始索引
nums = [[i, v] for i, v in enumerate(nums)]
nums = sorted(nums, key=lambda k: k[1], reverse=False)
算法源码：
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
# 2. 排序+双指针
nums = [[i, v] for i, v in enumerate(nums)]
nums = sorted(nums, key=lambda k: k[1], reverse=False)
start, end = 0, len(nums) - 1
while start < end:
tmp_sum = nums[start][1] + nums[end][1]
if tmp_sum < target:
start += 1
elif tmp_sum > target:
end -= 1
else:
return [nums[start][0], nums[end][0]]
return []
时间复杂度：O(NlogN)，其中先将数组排序好O(NlogN)，再双指针遍历O(N)得到结果
空间复杂度：O(N)，其中N是数组中的元素数量
哈希
- 上述方法查询
target - x时间复杂度较高，因此，为了更快速查询数组中是否有目标元素，我们可以使用索引。使用哈希表，可以将寻找target - x的时间复杂度降低从O(N)降低到O(1)
算法源码：
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
# 3. 哈希
hash_res = {}
for k, v in enumerate(nums):
if target - v in hash_res:
return [hash_res[target - v], k]
hash_res[v] = k
return []
时间复杂度：O(N)，其中N是数组中的元素数量。对于每一个元素 x，我们可以O(1)地寻找 target - x
空间复杂度：O(N)，其中N是数组中的元素数量。主要为哈希表的开销
三数之和
题目
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = []
输出：[]
示例 3：
输入：nums = [0]
输出：[]
提示：
0 <= nums.length <= 3000
-105 <= nums[i] <= 105
解题
排序 + 迭代1次 + 双指针
- 该题核心是
nums[k] + nums[i] + nums[j] = target公式，假如固定nums[k]很容易联想到两数之和(排序 + 双指针)解法。
原列表：[-1,0,1,2,-1,-4]
排序后：[-4,-1,-1,0,1,2]
^ ^ ^
固定k, i，j 双指针解法
- 故可以通过外层加一次循环遍历改造排序+双指针的解法，伪代码如下
for k, v in enumerate(nums[:-2]):
# 双指针解法
- 注意本题临界条件
len(nums) < 3判断和三元组不重复判断
算法源码：
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if len(nums) < 3: return [] # 临界判断
nums = sorted(nums, reverse=False)
res = set() # 去重
for i, v in enumerate(nums[:-2]):
if v > 0: break # 剪枝优化
start, end = i + 1, len(nums) - 1
while start < end:
if v + nums[start] + nums[end] > 0:
end -= 1
elif v + nums[start] + nums[end] < 0:
start += 1
else:
temp = (v, nums[start], nums[end])
# temp = sorted(temp, reverse=False) # 排序去除重复
res.add((temp[0], temp[1], temp[2]))
start += 1
return list(res)
时间复杂度：O(N^2)，排序O(NlogN) + 查询比较O(N^2)
空间复杂度：O(N)，其中N是数组中的元素数量
四数之和
题目
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [], target = 0
输出：[]
提示：
0 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109
解题
排序 + 迭代2次 + 双指针
- 该题核心是
nums[k] + nums[m] + nums[i] + nums[j] = target公式，假如固定nums[k]和nums[m]很容易联想到两数之和(排序 + 双指针)和三数之和的解法。 - 故可以通过外层加一次循环遍历改造三数之和的解法，伪代码如下
for k, v in enumerate(nums[:-3]):
# 三数之和解法
算法源码：
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
if len(nums) < 4: return []
nums = sorted(nums, reverse=False)
res = set() # 去重
for i, i_v in enumerate(nums[:-3]):
for j, j_v in enumerate(nums[i + 1:-2]):
start, end = i + j + 2, len(nums) - 1
while start < end:
sum_val = i_v + j_v + nums[start] + nums[end]
if sum_val > target:
end -= 1
elif sum_val < target:
start += 1
else:
temp = [i_v, j_v, nums[start], nums[end]]
# temp = sorted(temp, reverse=False)
res.add((temp[0], temp[1], temp[2], temp[3]))
start += 1
return list(res)
时间复杂度：O(N^3)，排序O(NlogN) + 查询比较O(N^3)
空间复杂度：O(N)，其中N是数组中的元素数量
N数之和
排序 + 递归迭代N-1次 + 双指针
- 有了两数之和、三数之和、四数之和，那么五数之和，以及 N 数之和...,那么有没有一种通用的方法呢？这块可以沿用这种通用模式，参考：实战 15.三数之和、18.四数之和，并扩展至 N 数之和
算法代码：
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
# 2.通用递归方法
def nSum(nums, n, target):
if len(nums) < n: return []
res = []
if n == 2:
left, right = 0, len(nums)-1
while left < right:
if nums[left] + nums[right] == target:
res.append([nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]: left += 1
while left < right and nums[right] == nums[right-1]: right -= 1
left += 1
right -= 1
elif nums[left] + nums[right] > target:
right -= 1
else:
left += 1
return res
else:
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i - 1]: continue
sub_res = nSum(nums[i + 1:], n - 1, target - nums[i])
for j in range(len(sub_res)): res.append([nums[i]] + sub_res[j])
return res
if len(nums) < 4: return []
nums = sorted(nums, reverse=False)
return nSum(nums, 4, target)
总结
- N数之和可通过最后模版代码通用处理，但由于整个核心是通过双指针减少一层遍历，故N值过大整体性能也受限
附录
- https://leetcode-cn.com/problems/two-sum/
- https://leetcode-cn.com/problems/3sum/
- https://leetcode-cn.com/problems/4sum/
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2021-04-12，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录