Summary

1. 移除元素 27. Remove Element (Array 3)
2. 反转字符串 344. Reverse String (String 1)
3. 替换空格 剑指Offer 05 (String 3)
4. 翻转字符串里的单词 151. Reverse Words in a String 🧡 (String 4)
5. 反转链表 206. Reverse Linked List (LinkedList 4)
6. 删除链表的倒数第N个节点19. Remove Nth Node From End of List🧡(LinkedList 6)
7. 链表相交160. Intersection of Two Linked Lists (LinkedList 7)
8. 环形链表II 142. Linked List Cycle II🧡 (LinkedList 8.2)
9. 三数之和 15. 3Sum🧡
10. 四数之和 18. 4Sum🧡

1. 移除元素 27. Remove Element (Array 3)

2. 反转字符串 344. Reverse String (String 1)

3. 替换空格 剑指Offer 05 (String 3)

4. 翻转字符串里的单词 151. Reverse Words in a String 🧡 (String 4)

5. 反转链表 206. Reverse Linked List (LinkedList 4)

6. 删除链表的倒数第N个节点19. Remove Nth Node From End of List🧡(LinkedList 6)

7. 链表相交160. Intersection of Two Linked Lists (LinkedList 7)

8. 环形链表II 142. Linked List Cycle II🧡 (LinkedList 8.2)

9. 三数之和 15. 3Sum🧡

使用双指针 Time O(n^2)
Hash 比较难完成剪枝和去重。所以使用双指针。
拿这个nums数组来举例，首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。

依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right]。

接下来如何移动left 和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。

如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。

操作

去重很重要

• a b去重
  说道去重，其实主要考虑三个数的去重。 a, b ,c, 对应的就是 nums[i]，nums[left]，nums[right]

a 如果重复了怎么办，a是nums里遍历的元素，那么应该直接跳过去。

但这里有一个问题，是判断 nums[i] 与 nums[i + 1]是否相同，还是判断 nums[i] 与 nums[i-1] 是否相同。

有同学可能想，这不都一样吗。

其实不一样！

都是和 nums[i]进行比较，是比较它的前一个，还是比较他的后一个。

如果我们的写法是 这样：

if (nums[i] == nums[i + 1]) { // 去重操作
    continue;
}

那就我们就把 三元组中出现重复元素的情况直接pass掉了。 例如{-1, -1 ,2} 这组数据，当遍历到第一个-1 的时候，判断 下一个也是-1，那这组数据就pass了。

我们要做的是 不能有重复的三元组，但三元组内的元素是可以重复的！

所以这里是有两个重复的维度。

那么应该这么写：

if (i > 0 && nums[i] == nums[i - 1]) {
    continue;
}

这么写就是当前使用 nums[i]，我们判断前一位是不是一样的元素，在看 {-1, -1 ,2} 这组数据，当遍历到 第一个 -1 的时候，只要前一位没有-1，那么 {-1, -1 ,2} 这组数据一样可以收录到 结果集里。

这是一个非常细节的思考过程。

• b c去重

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++){
            if(nums[i] > 0){
                return res; //最小值大于0，不可能配出来等于0
            }
            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){
                    left++;
                }else if(sum > 0){
                    right--;
                }else{
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    //对后两个元素去重
                    while(left < right && nums[right] == nums[right - 1]){
                        right--;
                    }
                    while(left < right && nums[left] == nums[left + 1]){
                        left++;
                    }
                    left++;
                    right--;
                }
            }
        }
        return res;
    }
}

10. 四数之和 18. 4Sum🧡

逻辑和上一个题一模一样， 只需要多加一层for loop
但剪枝判断不一样
不要判断nums[k] > target就返回了，三数之和 可以通过nums[i] > 0 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值。比如：数组是[-4, -3, -2, -1]，target是-10，不能因为-4 > -10而跳过。但是我们依旧可以去做剪枝，逻辑变成nums[i] > target && (nums[i] >=0 || target >= 0)就可以了。
Time O(n^3) （暴力O(N^4)）

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i++){
            if(nums[i] > 0 && nums[i] > target){
                return res;
            }
            if(i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            for(int j = i + 1; j < nums.length; j++){
                if(j > i + 1 && nums[j] == nums[j - 1]){
                    continue;
                }
                int left = j + 1;
                int right = nums.length - 1;
                while(left < right){
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if(sum < target){
                        left++;
                    }else if(sum > target){
                        right--;
                    }else{
                        res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        while(left < right && nums[right] == nums[right - 1]){
                            right--;
                    }
                        while(left < right && nums[left] == nums[left + 1]){
                            left++;
                    }
                        left++;
                        right--;
                    }
                }
            }
        }
        return res;
    }
}