/*
在数组中找所有3个数相加等于0的子数组
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
*/
class Solution { public: vector<vector<int> >* v; vector<vector<int>> threeSum(vector<int>& num) { v = new vector<vector<int> >(); if(num.size()<3) { return *v; } sort(num.begin(),num.end()); for(int i=0;i<num.size()-2;i++) { if(i>0 && num[i]==num[i-1]) continue; for(int j=i+1;j<num.size();j++) { if(j>i+1 && num[j]==num[j-1]) continue; int left = j+1; int right = num.size()-1; while(left<=right) { int mid = left+(right-left)/2; if(num[i]+num[j]+num[mid] == 0) { vector<int> tmp; tmp.push_back(num[i]); tmp.push_back(num[j]); tmp.push_back(num[mid]); v->push_back(tmp); break; } else if(num[i]+num[j]+num[mid]>0) { right = mid-1; } else { left = mid+1; } } } } return *v; } };
