1. 两数之和
题目描述
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
1.1 解法一
利用哈希字典({元素: 下标})的 O(1) 时间存取的特性.
扫描数组, 在字典中查找 target - num 元素, 如没找到则将当前扫描值记录一下.
算法复杂度 O(n).
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
num2idx = dict()
for i, num in enumerate(nums):
if target - num in num2idx:
return [num2idx[target - num], i]
else:
num2idx[num] = i
1.2 解法二
双指针法扫描有序数组: 该方法可以避免对原始数组进行暴力枚举时的冗余计算.
考虑数组 [a, b, c] 和目标值 target:
- 若 a + b == target, 则返回[a, b].
- 若 a + b != target, 则可能要分别计算 a + c 与 b + c.
以上是暴力枚举法的步骤. 但如果知道数组元素的序关系 a < c < b, 那么:
- 若 a + b < target, 则只需计算 c + b 即可;
- 若 a + b > target, 则只需计算 a + c 即可.
所以, 如果知道数组元素的序关系, 就可以优化计算. 特别是对于元素数量较大的数组, 可以大幅减少需要计算的二元组数量.
具体地, 先对数组进行排序, 然后初始化两个分别指向最小值和最大值的指针, 根据两指针指向的元素之和与target的大小关系, 决定移动哪个指针, 重复此步骤直至满足条件或数组扫描完毕.
排序复杂度 O(nlogn), 扫描复杂度 O(n), 故总体复杂度为O(nlogn).
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
idx_nums = [*zip(range(len(nums)), nums)]
idx_nums.sort(key = lambda x: x[1])
idx_vec, _ = zip(*idx_nums)
lo, hi = 0, len(nums) - 1
while lo < hi:
s = nums[idx_vec[lo]] + nums[idx_vec[hi]]
if s == target:
return [idx_vec[lo], idx_vec[hi]]
elif s < target:
lo += 1
else:
hi -= 1
return []
2. 三数之和
题目描述
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
解
先排序, 扫描数组, 在数组的后面部分寻找加和等于当前元素的相反数的两个数, 于是转化成两数之和问题, 可用1.2的算法解答. 只是该题目增加了去重操作, 这步操作也很简单, 因为数组已经排序, 相等元素必相邻, 所以重复的目标元素直接跳过, 重复的指针元素移动指针即可.
时间复杂度 O(n^2).
def threeSum(self, nums):
result = list()
if len(nums) < 3:
return result
nums.sort()
for i in range(len(nums)-2):
if i > 0 and nums[i] == nums[i-1]:
continue
lo, hi = i+1, len(nums)-1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s == 0:
result.append([nums[i], nums[lo], nums[hi]])
while lo < hi and nums[lo] == nums[lo+1]:
lo += 1
lo += 1
elif s < 0:
lo += 1
else:
hi -= 1
return result
3. K数之和
更一般地, 对于有序数组nums, 可用递归求解和为target的不重复的K元组.
def kSum(nums, target, k, prev, result):
if len(nums) < k or k < 2 or target < nums[0]*k or target > nums[-1]*k:
return []
if k == 2:
lo, hi = 0, len(nums)-1
while lo < hi:
s = nums[lo] + nums[hi]
if s == target:
result.append(prev+[nums[lo], nums[hi]])
while lo < hi and nums[lo] == nums[lo+1]:
lo += 1
lo += 1
elif s < target:
lo += 1
else:
hi -= 1
else:
for i in range(len(nums)-k+1):
if i == 0 or (i > 0 and nums[i] != nums[i-1]):
kSum(nums[i+1:], target-nums[i], k-1, prev+[nums[i]], result)
4. 四数之和
题目描述
给定一个包含 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]
]
解
K数之和的特例.
def fourSum(self, nums, target):
def kSum(lo, hi, target, k, prev, result):
if hi-lo+1 < k or k < 2 or target < nums[lo]*k or target > nums[hi]*k:
return []
if k == 2:
while lo < hi:
s = nums[lo] + nums[hi]
if s == target:
result.append(prev+[nums[lo], nums[hi]])
while lo < hi and nums[lo] == nums[lo+1]:
lo += 1
lo += 1
elif s < target:
lo += 1
else:
hi -= 1
else:
for i in range(lo, hi+1):
if i == lo or (i > lo and nums[i] != nums[i-1]):
kSum(i+1, hi, target-nums[i], k-1, prev+[nums[i]], result)
nums.sort()
result = list()
kSum(0, len(nums)-1, target, 4, [], result)
return result
