# 15. 3Sum

![](/files/-Ml3I_Z6Hs6yy4NjzQnQ)

## transform to two sum (in sorted array)

time: O(n^2)

space: O(k), k is the number of solutions

```java
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length < 3) {
            return res;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            
            if (i > 0 && nums[i] == nums[i-1]) { // ignore duplicate
                continue;
            }
            
            int target = -nums[i];
            int left = i+1, right = nums.length - 1;
            
            twoSum(res, nums, left, right, target);
        }
        return res;
        
    }
    // transform to two sum problem (in sorted array)
    private void twoSum(List<List<Integer>> res, int[] nums, int left, int right, int target) {
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                
                res.add(Arrays.asList(nums[left], nums[right], -target)); // add ans
                
                left++; // move into central at the same time, why, because only move one side, the value just equ...
                right--;
                while (left < right && nums[left] == nums[left-1]) { // ignore duplicate
                    left++;
                }
                while (left < right && nums[right] == nums[right+1]) { // ignore duplicate
                    right--;
                }
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
}
/*
brute force: O(n^3), three for loop to find ans

so optimized solution is: 
makes it like two sum: O(n^2)
a + b + c == 0

a + b = -c, become two sum(sorted), a+b find target -c

1. sort data
2. for (i = 0, ..i < nums.length -2...) target = -num[i]
3. two sum, but this need skip duplicate value

cant have duplicate ans
*/
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/two-pointer/15.-3sum.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.