day30【LeetCode力扣】18.四数之和

1.题目描述

给你一个由 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]]

提示：

1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109

2.题解

2.1 c++ 【排序+双指针】

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> res;sort(nums.begin(),nums.end());int length = nums.size();for(int i=0; i<length;i++){if(nums[i]>target&&target>0)break;if(i>0&&nums[i]==nums[i-1])continue;for(int j=i+1;j<length;j++){if(nums[i]+nums[j]>target&&target>0)break;if(j>i+1&&nums[j]==nums[j-1])continue;int left=j+1;int right=length-1;while(left<right){// long long s = static_cast<long long>(nums[i]) + nums[j] + nums[left] + nums[right];long s = (long)(nums[i]) + nums[j] + nums[left] + nums[right];if(s==target){res.push_back(vector<int>{nums[i],nums[j],nums[left],nums[right]});while(left<right&&nums[left]==nums[left+1])left++;while(left<right&&nums[right]==nums[right-1])right--;left++;right--;}else if(s<target)left++;elseright--;}}}return res;}
};

2.2 python【排序+双指针】

class Solution:def fourSum(self, nums: List[int], target: int) -> List[List[int]]:nums.sort()n = len(nums)res = []for i in range(n):if nums[i]>target and nums[i]>0 and target >0:breakif i>0 and nums[i]==nums[i-1]:continuefor j in range(i+1,n):if nums[i] + nums[j]>target and target>0:breakif j>i+1 and nums[j]==nums[j-1]:continueleft,right = j+1,n-1while left<right:sums = nums[i]+nums[j]+nums[left]+nums[right]if sums==target:res.append([nums[i],nums[j],nums[left],nums[right]])while left < right and nums[left]==nums[left+1]:left+=1while left < right and nums[right]==nums[right-1]:right-=1left+=1right-=1elif sums<target:left+=1else:right-=1return res

2.3 python【字典】

class Solution:def fourSum(self, nums: List[int], target: int) -> List[List[int]]:res_dict = {}for num in nums:res_dict[num]=res_dict.get(num,0)+1ans = set()for i in range(len(nums)):for j in range(i+1,len(nums)):for k in range(j+1,len(nums)):val = target-nums[i]-nums[j]-nums[k]if val in res_dict:count = (nums[i] == val) + (nums[j] == val) + (nums[k] == val)if res_dict[val]>count:ans.add(tuple(sorted([nums[i],nums[j],nums[k],val])))return [list(x) for x in ans]

排序的主要目的是为了避免重复。在这段代码中，将四个元素 [nums[i], nums[j], nums[k], val] 排序后，可以确保不同顺序的相同元素组合被视为同一个组合。这是因为排序后的元组是唯一的，无论元素的原始顺序如何。

具体来说，考虑这样一种情况：假设有两个四元组 (a, b, c, d) 和 (b, c, a, d)，它们的元素相同，但顺序不同。如果不排序，它们将被视为不同的项，并且都会被添加到集合 ans 中。而排序后，这两个四元组都会变成 (a, b, c, d)，从而确保集合 ans 中不会有重复的项。

ok了，就到这里叭～～～

如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！

成功并不是最终目的,而是持续努力的结果。

day30【LeetCode力扣】18.四数之和