> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/02-06-2022-15.md).

# 02/06/2022 15

Method: First sort the array. Then iterate each element at index i from 0 to its length, set left = i +1,

right to the last element. Check the sum of nums\[i], nums\[left],nums\[right]. If it is greater than 0, decrement right. If it is less than 0, increment left, else add to the result and also increment left and decrement right. Noted that when i > 0, we need to check if the current value is the same with the previous one. If it is, skip it.

Time O(n^2)

Space from O(logn) to O(n), depending on the implementation of the sorting algorithm.

```
    class Solution { 
    public List<List> threeSum(int[] nums) { 
    Arrays.sort(nums); 
    List<List> result = new ArrayList<>();
    for (int i = 0; i < nums.length; i++){ 
    // if the least value is greater than 0, return the empty list 
    if(nums[i] > 0) return result; 
    //if the current value is same with the previous one, just skip it 
    if( i > 0 && nums[i] == nums[i-1]) continue; 
    int left = i + 1; 
    int right = nums.length - 1;
    while(left < right){
        int sum = nums[i] + nums[left] + nums[right];
        if(sum > 0){
            right--;
        }else if(sum < 0){
            left++;
        }else{
            result.add(Arrays.asList(nums[i], nums[left],nums[right]));//need to remember this
            while(left < right && nums[left] == nums[left+1]) left++;
            while(left < right && nums[right] == nums[right-1]) right--;
            
            left++;
            right--;
        }
    }
}
    return result;        
}
```

}