【代码随想录day7】四数之和-Toy模板网

这篇具有很好参考价值的文章主要介绍了【代码随想录day7】四数之和。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按任意顺序返回答案。

示例 1：

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

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

思路

思路同三数之和，只不过在三数之和的基础上加了一层for循环，将复杂度从暴力的o(n^4)降为o(n^3)。其实此类题目都是类似解法，包括N数之和，都是在暴力的基础上降了o(n)的时间复杂度。文章来源地址https://www.toymoban.com/news/detail-544621.html

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        res = []
        for i in range(len(nums)):
            a = nums[i]
            # 对a去重
            if i>0 and a==nums[i-1]:
                continue
            for j in range(i+1,len(nums)):
                b = nums[j]
                # 对b去重
                if j>i+1 and b==nums[j-1]:
                    continue
                left, right = j+1, len(nums)-1
                
                while left<right:
                    sum_ = a+b+nums[left]+nums[right]
                    if sum_ > target:
                        right -= 1
                    elif sum_ < target:
                        left += 1
                    # 得到符合条件的a、b、c、d并去重
                    else:
                        res.append([a, b, nums[left], nums[right]])
                        # 对c去重
                        while left<right and nums[left]==nums[left+1]:
                            left += 1
                        # 对d去重
                        while left<right and nums[right]==nums[right-1]:
                            right -= 1
                        left += 1
                        right -= 1
        return res

到了这里，关于【代码随想录day7】四数之和的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！