题目描述:
给你一个由 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
c++代码:
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> v;
int n=nums.size();
if(n<4)return v;
sort(nums.begin(),nums.end());
map<vector<int>,int> m;
if(n==4){
long long sum=nums[0]+nums[1];
long long sum2=target-nums[2]-nums[3];
if(sum==sum2){
v.push_back(nums);
}
return v;
}
for(int i=0;i<n-3;i++){
int first=nums[i];
for(int j=i+1;j<n;j++){ //从后面的部分选第二个数
int second=nums[j];
int left=i+1,right=n-1;
while(left<right){
long long sum=nums[left]+nums[right];
long long sum2=target-first-second;
if(sum==sum2){
vector<int> vv;
vv.push_back(first);
vv.push_back(second);
vv.push_back(nums[left]);
vv.push_back(nums[right]);
sort(vv.begin(),vv.end());
if(left!=j&&right!=j&&m[vv]==0){
v.push_back(vv);
m[vv]++;
}
left++;
right--;
while(left<right&&(nums[left]==nums[left-1]||left==j))left++;
while(left<right&&(nums[right]==nums[right+1]||right==j))right--;
}
else if(sum>sum2){
right--;
}
else if(sum<sum2){
left++;
}
}
}
}
return v;
}
};
对数组从小到大排序,按照第一个数a<=第二个数b<=第三个数c<=第四个数d来查找。
for循环确定a和b,再在a后面剩余的数组中用双指针确定c和d,若c+d小了,left++,若c+d大了,right–。
用map判断当前组合是否记录过,若没有,则记录该结果,并更新该组合的map值+1。
最后返回记录的所有组合。
python代码:
class Solution(object):
def fourSum(self, nums, target):
v=[]
nums.sort()
n=len(nums)
if n<4:
return v
r={}
for i in range(0,n-3):
for j in range(i+1,n):
left = i+1
right = n-1
while left<right:
if nums[i]+nums[j]+nums[left]+nums[right]==target:
l = [nums[i],nums[j],nums[left],nums[right]]
l.sort()
ll = '#'.join('%s' % num for num in l)
if r.has_key(ll)==False and left!=j and right!=j:
r[ll]=1
left=left+1
right=right-1
while left<right and nums[left]==nums[left-1]:
left=left+1
while left<right and nums[right]==nums[right+1]:
right=right-1
elif nums[i]+nums[j]+nums[left]+nums[right]<target:
left=left+1
elif nums[i]+nums[j]+nums[left]+nums[right]>target:
right=right-1
for item in r.keys():
numss = item.split("#")
numsss=[int(i) for i in numss]
v.append(numsss)
return v
总结:
排序+双指针 常用于加快数组中的查找
python中a = ‘b’.join(’%s’ % num for num in c)可将列表c转化为以字符b划分的字符串a