双指针-四数之和与目标值相等
程序员文章站
2022-09-13 22:42:30
1、题目描述 双指针 三数之和,给定一个包含n 个整数的数组nums和一个目标值target,判断nums中是否存在四个元素 a,b,c和 d,使得a + b + c + d的值与target相等?找出所有满足条件且不重复的四元组。注意:答案中不......
1、题目描述
基础题:双指针 三数之和
给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。
注意:答案中不可以包含重复的四元组。
2、代码详解
使用四个指针(a<b<c<d)。
固定最小的a和b在左边,c=b+1,d=_size-1 移动两个指针包夹求解。
保存使得nums[a]+nums[b]+nums[c]+nums[d]==target的解。
- 偏大时d左移,偏小时c右移。c和d相遇时,表示以当前的a和b为最小值的解已经全部求得。
- b++,进入下一轮循环b循环,当b循环结束后。a++,进入下一轮a循环。
- 即(a在最外层循环,里面嵌套b循环,再嵌套双指针c,d包夹求解)
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
if not nums or len(nums) < 4:
return []
nums.sort()
res = []
# 四个指针(a<b<c<d)。固定最小的a和b在左边
# c=b+1,d=_size-1 移动两个指针包夹求解
for a in range(len(nums) - 3):
if a > 0 and nums[a] == nums[a - 1]: # 跳过重复元素,避免出现重复解
continue
# 以下代码与三数之和一样的
for b in range(a + 1, len(nums) - 2):
if b > a + 1 and nums[b] == nums[b - 1]: # 跳过重复元素,避免出现重复解
continue
c = b + 1
d = len(nums) - 1
while c < d:
sum = nums[a] + nums[b] + nums[c] + nums[d]
if sum == target:
res.append([nums[a], nums[b], nums[c], nums[d]])
# 判断左界和右界是否和下一位置重复,去除重复解
while c < d and nums[c] == nums[c + 1]:
c += 1
while c < d and nums[d] == nums[d - 1]:
d -= 1
# 同时将 L,R 移到下一位置,寻找新的解
c += 1
d -= 1
elif sum < target: # nums[L] 太小,L 右移
c += 1
else: # nums[R] 太大,R 左移
d -= 1
return res
nums = [1, 0, -1, 0, -2, 2]
target = 0
s = Solution()
print(s.fourSum(nums, target)) # [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
时间复杂度:O(N^3),a遍历O(N)里嵌套b遍历O(N)再嵌套c,d双指针O(N)--> O(N^3)。 暴力法O(N^4)。
本文地址:https://blog.csdn.net/IOT_victor/article/details/107169449