# Two pointers solution

• Algo:

1. modify the original question to this one: in an ordered array, find two numbers and their sum equals to target.
2. two pointers. One moves from start to end, and the other moves in the opposite direction. Each time one pointer moves based on value of sum.

``````class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
vector< vector<int> > ans;
if (num.empty())
return ans;

sort(num.begin(), num.end());

int n = num.size();
for (int i = 0; i < n - 2; ++i) {
if (i > 0 && num[i] == num[i - 1])
continue;

int target = -num[i];
int left = i + 1, right = n - 1;
while (left < right) {
int sum = num[left] + num[right];
if (right < n - 1 && num[right] == num[right + 1]) {
--right;
} else if (sum > target) {
--right;
} else if (sum < target) {
++left;
} else {
int t[] = {num[i], num[left], num[right]};
ans.push_back(vector<int>(t, t + 3));
++left;
--right;
}
}
}
return move(ans);
}
};``````

``````public List<List<Integer>> threeSum(int[] num) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(num.length<3)
return result;
Arrays.sort(num);
for(int i=0;i<num.length-2;i++){
if(i>0&&num[i]==num[i-1])
continue;
int j=i+1,k=num.length-1;
while(j<k){
if(num[i]+num[j]+num[k]==0){
List<Integer> list = new ArrayList<Integer>();
j++;
k--;
}else if(num[j]+num[k]<-1*num[i]){
j++;
}else if(num[j]+num[k]>-1*num[i]){
k--;
}
}

}
Set set = new HashSet(result);
List<List<Integer>> result2 = new ArrayList<List<Integer>>();
for(Object e:set){