# 3 Sum, 3 Sum Closest / Smaller, 4 Sum

### [3Sum](https://leetcode.com/problems/3sum/)

这题唯一的问题就是去重，三个指针都要注意一次迭代，同样只加一次，要靠 while 推一下。

* **result.add(Arrays.asList(nums\[i], nums\[j], nums\[k]));**
* **result.add(new int\[]{1,2,3});**

```java
public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
         List<List<Integer>> list = new  ArrayList<List<Integer>>();
         if(nums == null || nums.length == 0) return list;
         Arrays.sort(nums);

         for(int i = 0; i < nums.length - 2; i++){
             int left = i + 1;
             int right = nums.length - 1;
             while(left < right){
                 int sum = nums[i] + nums[left] + nums[right];
                 if(sum == 0){
                     list.add(Arrays.asList(nums[i], nums[left ++], nums[right --]));

                     while(left < right && nums[left] == nums[left - 1]) left ++;
                     while(left < right && nums[right] == nums[right + 1]) right --;
                 } else if(sum < 0){
                     left ++;
                 } else{
                     right --;
                 }
             }

             while(i < nums.length - 2 && nums[i] == nums[i + 1]) i++;
         }

         return list;
    }
}
```

## [3Sum Closest](https://leetcode.com/problems/3sum-closest/)

Trivial problem.

```java
public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        if(nums == null || nums.length < 3) return -1;

        int curMin = Math.abs(nums[0] + nums[1] + nums[2] - target);
        int curSum = nums[0] + nums[1] + nums[2];

        Arrays.sort(nums);

        for(int i = 0; i < nums.length - 2; i++){
            int left = i + 1;
            int right = nums.length - 1;
            while(left < right){
                int sum = nums[i] + nums[left] + nums[right];
                if(sum == target){
                    return sum;
                } else if(sum < target){
                    left ++;
                } else if(sum > target){
                    right --;
                }

                if(Math.abs(sum - target) < curMin){
                    curMin = Math.abs(sum - target);
                    curSum = sum;
                }
            }
        }

        return curSum;
    }
}
```

## [3Sum Smaller](https://leetcode.com/problems/3sum-smaller/)

更有意思一点的双指针题\~ 姿势水平比前几道高，利用 sum < target 时，i 和 left 不动，介于 left 和 right (包括 right) 之间的所有元素 sum 也一定小于 target 的单调性。

```java
public class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        if(nums == null || nums.length < 3) return 0;

        int count = 0;
        Arrays.sort(nums);

        for(int i = 0; i < nums.length - 2; i++){
            int left = i + 1;
            int right = nums.length - 1;
            while(left < right){
                int sum = nums[i] + nums[left] + nums[right];
                if(sum >= target){
                    right --; 
                } else {
                    count += (right - left);
                    left ++;
                }
            }
        }

        return count;
    }
}
```

## [4Sum](https://leetcode.com/problems/4sum/)

稍微 gay 了点，但是优化空间变大了，处理的好的话，可以超过 96.09 % \~

* **每一轮的指针都要注意去重；**
* **每一轮进入内循环之前，可以直接看一眼 index 与**
  * **index 后面的连续几个数**
  * **nums\[] 末尾的最后几个数**
* **是不是会比 target 小或者大，如果 index 与后面连续的几个数加起来都没 target 大，那么检查这个 index 的必要都没有，可以直接跳过；如果 index 与最末尾的几个数相加依然小于 target，那么说明我们应该直接去看下一个更大的数当 index.**

```java
public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> total = new ArrayList<>();
        int n = nums.length;
        if(n < 4) return total;

        Arrays.sort(nums);

        for(int i = 0; i < n - 3;i++)
        {
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            if(nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
            if(nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) continue;

            for(int j = i + 1; j < n - 2; j++)
            {
                if(j > i + 1 && nums[j] == nums[j - 1]) continue;
                if(nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
                if(nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) continue;

                int left = j + 1, right = n - 1;
                while(left < right){
                    int sum = nums[left] + nums[right] + nums[i] + nums[j];
                    if(sum < target) left++;
                    else if(sum > target) right--;
                    else{
                        total.add(Arrays.asList(nums[i],nums[j],nums[left++],nums[right--]));

                        while(left < right && nums[left] == nums[left - 1]) left ++;
                        while(left < right && nums[right] == nums[right + 1]) right --;
                    }
                }
            }
        }
        return total;
    }
}
```


---

# 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://mnunknown.gitbook.io/algorithm-notes/two_pointers/3_sum-_3_sum_closest__smaller-_4_sum.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.