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了，就到這里叭～～～

? 如果覺得作者寫的不錯，求給博主一個大大的點贊支持一下，你們的支持是我更新的最大動力！

? 如果覺得作者寫的不錯，求給博主一個大大的點贊支持一下，你們的支持是我更新的最大動力！

? 如果覺得作者寫的不錯，求給博主一個大大的點贊支持一下，你們的支持是我更新的最大動力！

成功并不是最終目的,而是持續努力的結果。