这里记录这一题，也是告诉自己，在遇到这一类题的时候，思路要清晰，遇到重复问题，不能够当遇到时加个别判例，而是一开始就要分情况处理好;
题目：
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
这一题，拿到手里，就知道这是一个回溯算法，但是这里关键的问题就是如何去解决重复问题;我一开始就把回溯的解法放上去，然后加了一个判断重复的处理条件，然后就开始跑，于是又遇到一个重复情况，于是我想着又加，这里关键问题就是，我原来的逻辑结构，并不适合加这些重复条件的判断，或者这样加特别复杂，即被你搞麻烦了，于是我就耗时的去想，还是会出现重复的情况，所以下一次遇到的时候，就应该处理好重复情况，然后根据重复情况来选择逻辑结构;
虽然，最后我挤破脑袋，想出来了，但是超出时间限制。。。，于是我在自己的电脑上跑了一下，是对的;
我的思路就是先排个序，然后依次向后累加，与target比较，
#include <vector> #include <iostream> #include <algorithm> using namespace std; class Solution { public: int backthrough(vector<int> &num,int index,vector<int> res,int src,int target,vector<vector<int>> &gu){ int k=0; int SIZE=num.size(); if(index<num.size()&&(src+num[index]==target)&&res.size()==3){ res.push_back(num[index]); gu.push_back(res); //如果正好，则说明下一次最后一个数要在index之前 return index-1; }else if(res.size()==3){ //index不符合，则index向后移动 //其实可以加判断，就是大于target就不要向后移动了 //我的加了之后，会报错，说明我的这个逻辑结构不行 index+=1; } else if(res.size()==4&&src==target){ gu.push_back(res); //如果正好，则说明下一次最后一个数要在index-2之前 //因为这里的index并不是正好的最后一个数，而是i+1， //所以最后一个是index-1，因此下一次要在0～index-2中选 return index-2; } else if((res.size()==4&&src!=target)||(res.size()+(num.size()-index))<4){ return 0; } for(int i=index;i<SIZE;++i) { //防止第一位和第二位 if(i>0&&((res.size()==1&&res.back()!=num[i])||res.size()==0)&&(num[i-1]==num[i])) continue; res.push_back(num[i]); k=backthrough(num,i+1,res,src+num[i],target,gu); if(k){ //第三位 //成功的话，后面还有一样的就直接跳过 while(i+1<num.size()&&num[i+1]==num[i]){ ++i; } //跳过最后一个数还是重复的 //第四位 SIZE=k; } res.erase(res.end()-1); } //这样返回的SIZE必定是最小的那个，避免上一个循环去选择重复的 return SIZE; } vector<vector<int>> fourSum(vector<int>& nums, int target) { std::sort(nums.begin(),nums.end()); vector<vector<int>> gu; vector<int> res; backthrough(nums,0,res,0,target,gu); return gu; } };这里进行了四次循环，所以是O(n^4)
其实我有想到利用双指针，掐头去尾，但是我的这个代码逻辑结构不是和这么写，或者我想不到;
于是看了别人的答案，思路特别的清晰，和我判断的情况是一样的，但是人家却写的很清晰，需要学习
class Solution{ public: vector<vector<int>> fourSum(vector<int>& nums, int target) { sort(nums.begin(),nums.end()); vector<vector<int> > res; if(nums.size()<4) return res; int a,b,c,d,_size=nums.size(); for(a=0;a<=_size-4;a++){ if(a>0&&nums[a]==nums[a-1]) continue; //确保nums[a] 改变了 for(b=a+1;b<=_size-3;b++){ if(b>a+1&&nums[b]==nums[b-1])continue; //确保nums[b] 改变了 c=b+1,d=_size-1; while(c<d){ if(nums[a]+nums[b]+nums[c]+nums[d]<target) c++; else if(nums[a]+nums[b]+nums[c]+nums[d]>target) d--; else{ res.push_back({nums[a],nums[b],nums[c],nums[d]}); while(c<d&&nums[c+1]==nums[c]) //确保nums[c] 改变了 c++; while(c<d&&nums[d-1]==nums[d]) //确保nums[d] 改变了 d--; c++; d--; } } } } return res; } };
