首页 > 代码库 > 4Sum
4Sum
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:
- Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
- The solution set must not contain duplicate quadruplets.
For example, given array S = {1 0 -1 0 -2 2}, and target = 0. A solution set is: (-1, 0, 0, 1) (-2, -1, 1, 2) (-2, 0, 0, 2)C++代码实现：
#include<iostream>#include<algorithm>#include<vector>using namespace std;class Solution{public: vector<vector<int> > fourSum(vector<int> &num,int target) { if(num.empty()) return vector<vector<int> >(); sort(num.begin(),num.end()); vector<vector<int> > ret; int n=num.size(); int i,j; for(i=0; i<n-3; i++) { //只保留第一个不重复的，其余的都删了,因为left会选择重复的 if(i>=1&&num[i]==num[i-1]) continue; for(j=n-1; j>i+2; j--) { //只保留最后一个不重复的，其余的都删了,因为right会选择重复的 if(j<n-1&&num[j+1]==num[j]) continue; int left=i+1; int right=j-1; vector<int> tmp; while(left<right) { //只保留最后一个不重复的，其余的都删了,因为left会选择重复的 if(right<j-1&&num[right]==num[right+1]) right--; else if(num[i]+num[j]+num[left]+num[right]==target) { tmp= {num[i],num[left],num[right],num[j]}; ret.push_back(tmp); left++; right--; } else if(num[i]+num[j]+num[left]+num[right]<target) left++; else if(num[i]+num[j]+num[left]+num[right]>target) right--; } } } return ret; }};int main(){ vector<int> vec= {-5,5,4,-3,0,0,4,-2}; Solution s; vector<vector<int> > result=s.fourSum(vec,4); for(auto a:result) { for(auto v:a) cout<<v<<" "; cout<<endl; } cout<<endl;}
注意处理重复的vector。。。。
4Sum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。