18.四数之和

https://leetcode-cn.com/problems/4sum/

难度：中等

题目：

给定一个包含n 个整数的数组nums和一个目标值target，判断nums中是否存在四个元素 a，b，c和 d，

使得a + b + c + d的值与target相等？找出所有满足条件且不重复的四元组。

注意：答案中不可以包含重复的四元组。

提示：

• 0 <= nums.length <= 200
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9

示例：

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [], target = 0
输出：[]

分析

如果之前做过 两数之和 ,
三数之和 ,
那么，这道题就是无脑多嵌套一层for循环了...

双层for循环判断num1和num2，然后使用双指针执行while循环，直到left == right截止。

解题：

class Solution:
    def fourSum(self, nums, target):
        nums.sort()
        ln = len(nums)
        ret = []
        if ln < 4:
            return []
        for i in range(0, ln - 3):
            num1 = nums[i]
            for j in range(i + 1, ln - 2):
                num2 = nums[j]
                left = j + 1
                right = ln - 1
                while left < right:
                    total = num1 + num2 + nums[left] + nums[right]
                    if total == target:
                        tmp = [num1, num2, nums[left], nums[right]]
                        if tmp not in ret:
                            ret.append(tmp)
                        right -= 1
                    elif total < target:
                        left += 1
                    else:
                        right -= 1
        return ret

欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。

我的个人博客：https://qingfengpython.cn

力扣解题合集：https://github.com/BreezePython/AlgorithmMarkdown