Easy java solution with N times two pointer search

• ``````/**
* 1.Sort.
* 2.For each element, run two pointer search in ordr to find element + two values == 0
* 3.Avoid duplicates: in each element; in 2 pointer search.
* 4.Guard array index : left < right
*
* nlogn + n elemtn * O(n) each two pointer = O(n^2)
*/
public class Solution {
public List<List<Integer>> threeSum(int[] ns) {
List<List<Integer>> ret = new ArrayList<>();
if(ns == null || ns.length <= 2)
return ret;

// sort
Arrays.sort(ns);

// n times:  two pointers search.
for(int i =0; i < ns.length -2 ; i++){
int min = ns[i];
// min is largerthan zero, therefore sum is larger than zero, cannot be == 0
if(min >0)
break;

// skip duplicates.
if(i >0 && ns[i-1] == ns[i])
continue;

// two pointer search
int left = i +1;
int right = ns.length -1;
while(left < right){
int sum = min + ns[left] + ns[right];
if(sum == 0){
// accumulate ret
/* avoid duplicate;*/
while(left < right && ns[left] == ns[left +1])
left ++;
while(left < right && ns[right] == ns[right -1])
right --;
}
if(sum >0){
// decrease sum
right --;
}
else{
// increase sum
left ++;
}
}
}

return ret;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.