思路:
在三数之和的基础上加一层循环即可,注意跳过相等的元素。
代码如下,思路也可以看看我的注释:
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { //先从小到大进行排序 sort(nums.begin(),nums.end()); //存放结果 vector<vector<int>> result; //数组大小 int size=nums.size(); //选择第一个数 for(int a=0;a<size-3;++a) { //如果当前选择的第一个数与之前选择的第一个数重合了则跳过 if(a>0&&nums[a]==nums[a-1])continue; //选第二个数 for(int b=a+1;b<size-2;++b)//以下代码与三数之和一样的 { //如果当前选择的第二个数与之前选择的第二个数重合了则跳过 if(b>a+1&&nums[b]==nums[b-1])continue; //选择第三个数和第四个数,一个在左,一个在右端 int start=b+1,end=size-1; //进行查找比对sum while(start<end) { //求和 int sum=nums[a]+nums[b]+nums[start]+nums[end]; //如果当前的和小于目标,则加大当前的小值第三个数 if(sum<target) start++; //如果当前的和大于目标,则减小当前的大值第四个数 else if(sum>target) end--; //如果sum==target else{ //压入结果 result.push_back(vector<int>{nums[a],nums[b],nums[start],nums[end]}); //如果下一个第三个数的值与当前第三个数相等则跳过 while(start<end&&nums[start+1]==nums[start]){ start++; } //如果下一个第四个数的值与当前第四个数相等则跳过 while(start<end&&nums[end-1]==nums[end]){ end--; } //最后要再加一遍,可以跳过相等的,可以想象没有上面的相等也要进行向前走 start++; end--; } } } } return result; } };