欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

双指针-四数之和与目标值相等

程序员文章站 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

相关标签: 双指针