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

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