# simple solution with O(n^2) Algorithm complexity

• First, sort the nums by Arrays.sort(); Algorithm complexity is O(n log n);
then, use i point to the start position, j point the next of i, k point to the tail;
Three condition: the sum of these three num higher, lower, or equal to zero;
Three solution:
higher: we need the highest num become lower, so k--;
lower: the opposite of higher condition, j++;
equal: add to the ArrayList<Integer> and save into the HashSet<List<Integer>>. Except this condition, we ignore the other nums between j and k, so j++, k--;
'''
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);

``````	Set<List<Integer>> set = new HashSet<List<Integer>>();
int len = nums.length;
int i = 0;
int j = 0;
int k = 0;
while(i < len) {
j = i + 1;
k = len - 1;
while( j < k ) {
if((nums[i] + nums[j] + nums[k]) < 0) {
j++;
}else if((nums[i] + nums[j] + nums[k]) > 0){
k--;
}else {
List<Integer> subList = new ArrayList<Integer>();
j++;
k--;
}
}
i++;
}
return new ArrayList<>(set);
}
``````

'''

• You can save 5 lines in the else { by never naming subList:

`set.add(Arrays.asList(nums[i], nums[j], nums[k]));`

And 2 more by making the outer `while` loop a `for` loop:

``````int len...
for(int i = 0; i < len; i++) {
int j = i + 1;
int k = len - 1;
while ( j < k ) {
...
}
}
return...
``````

Also, since the input array was sorted, you can avoid any Set<List> and form the returned List<List> directly by continuing to increment j until nums[j] is a different number (or j >= k) whenever j is incremented, and vice versa for k (whenever k is decremented, continue decrementing k until nums[k] has a different value, or k <= j) to avoid duplicate triplets. That results in more lines and doesn't help overall time complexity, but it does avoid use of Set.

• This post is deleted!

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