题干
18. 四数之和
给定一个包含 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]
]
思路
这道题，和前面的三数之和相比，完全就是多了一层循环，不知道还有没有优化的算法
即在使用双指针之前先固定两个值
Python（最直接的代码）
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
n = len(nums)
if n < 4:
return []
nums = sorted(nums)
ans = []
for index1 in range(n - 3):
if index1 > 0 and nums[index1] == nums[index1 - 1]:
continue
for index2 in range(index1 + 1, n - 2):
if index2 > index1 + 1 and nums[index2] == nums[index2 - 1]:
continue
start, end = index2 + 1, n - 1
cmpValue = target - (nums[index1] + nums[index2])
while start < end:
if nums[start] + nums[end] == cmpValue:
ans.append([nums[index1], nums[index2], nums[start], nums[end]])
start += 1
end -= 1
while start < end and nums[start] == nums[start - 1]: start += 1
while start < end and nums[end] == nums[end + 1]: end -= 1
elif nums[start] + nums[end] > cmpValue:
end -= 1
else:
start += 1
return ans
- 此代码消耗资源情况如下
执行结果：
通过
显示详情
执行用时 :1240 ms, 在所有 Python3 提交中击败了38.73%的用户
内存消耗 :13.8 MB, 在所有 Python3 提交中击败了6.52%的用户
Python稍加优化
对于这道题有一个事实是
由于整个list要使用双指针必须先排序，即该list是递增的
所以当我们固定的两个值之和大于target并且大于0时，后面双指针再计算只能使得四数之和越来越大，这样的计算是毫无意义的，所以可以进行适当的剪枝。
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
n = len(nums)
if n < 4:
return []
nums = sorted(nums)
ans = []
for index1 in range(n - 3):
if index1 > 0 and nums[index1] == nums[index1 - 1]:
continue
if nums[index1] > 0 and nums[index1] > target: # 剪枝
break
for index2 in range(index1 + 1, n - 2):
if index2 > index1 + 1 and nums[index2] == nums[index2 - 1]:
continue
if nums[index2] > 0 and nums[index1] + nums[index2] > target: # 剪枝
break
start, end = index2 + 1, n - 1
cmpValue = target - (nums[index1] + nums[index2])
while start < end:
if nums[start] + nums[end] == cmpValue:
ans.append([nums[index1], nums[index2], nums[start], nums[end]])
start += 1
end -= 1
while start < end and nums[start] == nums[start - 1]: start += 1
while start < end and nums[end] == nums[end + 1]: end -= 1
elif nums[start] + nums[end] > cmpValue:
end -= 1
else:
start += 1
return ans
这样得到的结果也会相对优化
执行用时 :856 ms, 在所有 Python3 提交中击败了54.40%的用户
内存消耗 :13.7 MB, 在所有 Python3 提交中击败了6.52%的用户
Python 进一步优化
对双指针法的头尾指针都使用二分法来提前定位到最接近的位置，能起到较大的优化作用
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
n = len(nums)
if n < 4:
return []
nums = sorted(nums)
ans = []
for index1 in range(n - 3):
if index1 > 0 and nums[index1] == nums[index1 - 1]:
continue
if nums[index1] > 0 and nums[index1] > target:
break
for index2 in range(index1 + 1, n - 2):
if index2 > index1 + 1 and nums[index2] == nums[index2 - 1]:
continue
if nums[index2] > 0 and nums[index1] + nums[index2] > target:
break
cmpValue = target - (nums[index1] + nums[index2])
end = n - 1
start = max(index2 + 1, bisect.bisect_left(nums, cmpValue - nums[end], index2 + 1, end) - 1) # 对头指针用二分法进行定位
end = min(end, bisect.bisect_right(nums, cmpValue - nums[start], start, end) + 1) # 对尾指针用而二分法进行定位
while start < end:
if nums[start] + nums[end] == cmpValue:
ans.append([nums[index1], nums[index2], nums[start], nums[end]])
start += 1
end -= 1
while start < end and nums[start] == nums[start - 1]: start += 1
while start < end and nums[end] == nums[end + 1]: end -= 1
elif nums[start] + nums[end] > cmpValue:
end -= 1
else:
start += 1
return ans
执行结果：通过
执行用时 :336 ms, 在所有 Python3 提交中击败了62.28%的用户
内存消耗 :13.6 MB, 在所有 Python3 提交中击败了6.52%的用户
