尚未完结，后续会不定时更新

1 哈希

1.1 1-1.两数之和🟢

题目：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

链接：1. 两数之和

示例 ：

输入：nums = [3,3], target = 6
输出：[0,1]

思路：

两个 for 循环可以解决，但第2个 for 循环可以用哈希表来快速查，不用一个个遍历

代码：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            // 查表，看看是否有能和 nums[i] 凑出 target 的元素
            int need = target - nums[i];
            if (hashMap.containsKey(need)) {
                return new int[]{hashMap.get(need), i};
            }
            // 查不到则存入映射，这样只用一次for循环
            hashMap.put(nums[i], i);
        }
        return null;
    }
}

1.2 2-49.字母异位词分组🟡

题目：给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

链接：49. 字母异位词分组

示例 ：

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

思路：

难点在于怎么判断哪些单词属于异味词，因为不能直接用 == 来判断。

观察异位词的特点可以看出他们排序后可以用 == 来直接判断

代码：

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> hashMap = new HashMap<>();
        for (String str : strs) {
            // 字符串转换成数组对字符串的字符排序
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            // 获取key对应的集合，若不存在则返回一个空集合
            List<String> list = hashMap.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            hashMap.put(key, list);
        }
        return new ArrayList<>(hashMap.values());
    }
}

1.3 3-128.最长连续序列🟡

题目：给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

链接：128. 最长连续序列

示例 ：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

思路：

利用哈希集和可以快速判断 nums 是否存在某个数字。

遍历 nums，若存在 num-1，说明当前数字不是该连续序列的起始值，从而过滤掉一些情况。之后不断用哈希集和判断是否存在序列的下一个数值

代码：

class Solution {
    public int longestConsecutive(int[] nums) {
        // 转化成哈希集合，不需要HashMap，只关注是否存在
        Set<Integer> set = new HashSet<Integer>();
        for (int num : nums) {
            set.add(num);
        }
        int res = 0;
        for (int num : set) {
            // num 不是连续子序列的第一个，跳过
            if (set.contains(num - 1)) {
                continue;
            }
            // num 是连续子序列的第一个，开始向后计算连续子序列的长度
            int curNum = num;
            int curLen = 0;
            while (set.contains(curNum)) {
                curNum += 1;
                curLen += 1;
            }
            // 更新最长连续序列的长度
            res = Math.max(res, curLen);
        }
        return res;
    }
}

2 双指针

2.1 4-283.移动零🟢

题目：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

链接：283. 移动零

示例 ：

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

思路：

快指针遍历数组，慢指针记录数组下一个不为0元素的位置。

快指针遇到不为0的元素时，与慢指针的位置进行交换即可

代码：

class Solution {
    public void moveZeroes(int[] nums) {
        int left = 0, right = 0;
        while (right < nums.length) {
            if (nums[right] != 0) {
                // 这里也可以用nums[left] = nums[right]
                // 然后把left及其后面的元素赋为0
                swap(nums, left, right);
                left++;
            }
            right++;
        }
    }

    public void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

2.2 6-15.三数之和🟡

题目：给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意： 答案中不可以包含重复的三元组。

链接：15. 三数之和

题解详细解释：三数之和

示例 ：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

思路：

3个 for 循环会超时，所以要优化。有重复元素，用哈希表也会比较麻烦

可以一个 for 循环遍历第1个数，剩余两个数不能用 for 循环的话，可以用双指针优化查找时间。

事先排序后，左右各一个指针。计算当前3个数字的和比目标值0大还是小，进而移动左指针(和会变大)或右指针(和会变小)。这样就可以减少循环次数，但要注意去重

代码：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        // 找出a + b + c = 0
        // a = nums[i], b = nums[left], c = nums[right]
        for (int i = 0; i < nums.length; i++) {
            // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组
            if (nums[i] > 0) {
                return res;
            }

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

            int left = i + 1;
            int right = nums.length - 1;
            while (right > left) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // 去重b和c，应该放在找到一个三元组之后
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;

                    right--;
                    left++;
                }
            }
        }
        return res;
    }
}

2.3 7-11.盛最多水的容器🟡

题目：给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明： 你不能倾斜容器。

链接：11. 盛最多水的容器

示例 ：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

思路：

最直观的是两个 for 循环遍历所有结果，但这样会超时，所以要进行优化

用双指针，一个指向左边，一个指向右边。最大水量取决于宽度和高度。而高度取决于 left 和 right 中较小的那个，比如 left 较小，那么移动 right 只会让高度不变或者更小，所以要移动高度较低的那条线，这样虽然宽度减小，但是高度有可能增大，容量才有可能变大

抽象成二维数组，因为每次移动都会排除一行或一列，所以不会遗漏

代码：

class Solution {
    public int maxArea(int[] height) {
        int res = 0, left = 0, right = height.length - 1;
        while (left < right) {
	        // 每次移动高度最短的那条线
            if (height[left] < height[right]) {
                res = Math.max(res, (right - left) * height[left]);
                left++;
            } else {
                res = Math.max(res, (right - left) * height[right]);
                right--;
            }
        }
        return res;
    }
}

2.4 8-42.接雨水🔴

题目：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

链接：42. 接雨水

示例 ：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

思路：

可以只关注某一个位置能接到多少雨水，应该是 min(左边最高的柱子,右边最高的柱子)-当前高度

但是计算某一侧最高的柱子要是每次都一个个遍历太耗时，可以使用备忘录的方式先提前算出所有位置两侧最高柱子的高度

不过上述题解要定义数组，空间复杂度为 O(n)，可以使用双指针进一步优化。思路还是对于每个位置用上面的公式计算当前位置能接多少雨水，不过是左右两个指纹向内移动。用两个变量取代之前的两个备忘录数组。

代码：

1.动态规划解法

class Solution {
    public int trap(int[] height) {
        if (height.length == 0) {
            return 0;
        }
        int n = height.length;
        int res = 0;
        // 数组充当备忘录
        int[] l_max = new int[n];
        int[] r_max = new int[n];
        // 初始化 base case
        l_max[0] = height[0];
        r_max[n - 1] = height[n - 1];
        // 从左向右计算 l_max
        for (int i = 1; i < n; i++)
            l_max[i] = Math.max(height[i], l_max[i - 1]);
        // 从右向左计算 r_max
        for (int i = n - 2; i >= 0; i--)
            r_max[i] = Math.max(height[i], r_max[i + 1]);
        // 计算答案 当前位置能接到的雨水取决于min(左,右最高的柱子)-当前高度
        for (int i = 1; i < n - 1; i++)
            res += Math.min(l_max[i], r_max[i]) - height[i];

        return res;
    }
}

2.双指针

class Solution {
    int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int lMax = 0, rMax = 0;

        int res = 0;
        while (left < right) {
            lMax = Math.max(lMax, height[left]);
            rMax = Math.max(rMax, height[right]);

            // res += min(lMax, rMax) - height[i]
            if (lMax < rMax) {
                res += lMax - height[left];
                left++;
            } else {
                res += rMax - height[right];
                right--;
            }
        }
        return res;
    }
}

3 滑动窗口

滑动窗口就两步：

• 右指针不断右移，每一次右移要不要做些额外处理
• 判断左侧窗口是否要收缩，若收缩应该怎么处理

无论右移还是收缩都是更改字符在window 对应的数值并更新指针

3.1 9-3.无重复字符的最长子串🟡

题目：给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

链接：3. 无重复字符的最长子串

示例 ：

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

思路：

子串问题那就要用双指针，这题更准确点是用双指针维护一个滑动窗口。

对于当前待添加的元素，若当前滑动窗口含有该元素，则需要删除滑动窗口左侧元素。直到滑动窗口不再包含该元素后，再把该元素添加到滑动窗口，每次添加后判断是否更新 res

代码：

1. HashSet：添加前先收缩

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> window = new HashSet<>();

        int left = 0, right = 0;
        int res = 0; // 记录结果
        while (right < s.length()) {
            char cur = s.charAt(right);
            // 无重复，窗口右指针右移增大窗口
            if (!window.contains(cur)) {
                window.add(cur);
                right++;
                // 更新最长不重复子串的长度
                res = Math.max(res, window.size()); 
            // 有重复，左指针右移缩小窗口，直到无重复
            } else {
                char d = s.charAt(left);
                window.remove(d);
                left++;
            }
        }
        return res;
    }
}

2.模板：先添加，再收缩

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> window = new HashMap<>();

        int left = 0, right = 0;
        int res = 0; // 记录结果
        while (right < s.length()) {
	        // 窗口右指针不断右移
            char cur = s.charAt(right);
            window.put(cur, window.getOrDefault(cur, 0) + 1);
            right++; 
            // 判断左侧窗口是否要收缩
            while (window.get(cur) > 1) {
                char d = s.charAt(left);
                window.put(d, window.get(d) - 1);
                left++;
            }
            // 在这里更新答案
            res = Math.max(res, right - left);
        }
        return res;
    }
}

3.2 10-438.找到字符串中所有字母异位词🟡

题目：给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

链接：438. 找到字符串中所有字母异位词

示例 ：

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

思路：

子串的处理仍然是用滑动窗口解决。本题要找的子串的长度是固定的，也就是可以看作是一个固定长度的滑动窗口不断右移，判断当前窗口的子串是否满足条件即可。

因为只有小写字母，所以可以用长度为26的数组记录每个字母出现的个数。然后判断两个字符串是否满足条件就可以转换为判断两个数组内的值是否相等，需要用 Arrays.equals(arr1,arr2)，注意不能用 arr1.equals(arr2)

用模板则是用一个 count 来记录有效数量是否达到要求，右移的时候判断是否要 ++，左侧收缩时判断是否要 --。

注意要做两步判断，首先是判断当前字符是否在目标字符串 p 中，即使在还要判断当前字符的个数是否和 p 的相同。例如，abb 的第3位 b 虽然也在 abc 中，但 b 的数量不同

代码：

1.滑动窗口-数组版

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();

        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }

        List<Integer> ans = new ArrayList<Integer>();
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        for (int i = 0; i < pLen; ++i) {
            ++sCount[s.charAt(i) - 'a'];
            ++pCount[p.charAt(i) - 'a'];
        }

        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }

        for (int i = 0; i < sLen - pLen; ++i) {
            --sCount[s.charAt(i) - 'a'];
            ++sCount[s.charAt(i + pLen) - 'a'];

            if (Arrays.equals(sCount, pCount)) {
                ans.add(i + 1);
            }
        }

        return ans;
    }
}

2.滑动窗口-模板版

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        for (char c : p.toCharArray())
            need.put(c, need.getOrDefault(c, 0) + 1);

        int left = 0, right = 0;
        int count = 0;
        List<Integer> res = new ArrayList<>();
        while (right < s.length()) {
            // 1.窗口右指针不断右移
            char cur = s.charAt(right);
            right++;
            // 右移的时候判断是否更新count
            if (need.containsKey(cur)) {
                window.put(cur, window.getOrDefault(cur, 0) + 1);
                // abb 的第3位b虽然也在abc中，但b的数量不同
                if (window.get(cur).equals(need.get(cur)))
                    count++;
            }
            // 2.判断左侧窗口是否要收缩
            while (right - left >= p.length()) {
                // 当窗口符合条件时，把起始索引加入 res
                if (count == need.size())
                    res.add(left);
                // 收缩时的处理
                char d = s.charAt(left);
                left++;
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d)))
                        count--;
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return res;
    }
}

4 子串

4.1 11-560.和为 K 的子数组🟡

题目：给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。其中， -1000 <= nums[i] <= 1000。

链接：560. 和为 K 的子数组

示例 ：

输入：nums = [1,2,3], k = 3
输出：2

思路：

因为 nums 里有负数，所以没法用滑动窗口。最简单的思路就是从当前数开始向后算出所有的子数组。

子数组是连续的，某一段位置 [j,...i] 的和若为 k，那不就是当前位置 i 的前缀和减去位置 j-1 的前缀和等于 k。这里我们只关系次数，并不关心这个 j 到底是多少，所以可以用 HashMap 存储前缀和，值为前缀和出现的次数。

从下标0到当前位置前缀和为 preSum， 若当前找到了 preSum - k，说明从0到当前位置分成了两部分：preSum - k 和 k，那就说明找到了合适的子数组

代码：

public class Solution {
    public int subarraySum(int[] nums, int k) {
        int res = 0, preSum = 0;
        // 前缀和为键，出现次数为对应的值
        Map<Integer, Integer> mp = new HashMap<>();
        // 后面get的时候，若preSum等于k会get(0)，所以0对应的值为1
        mp.put(0, 1);
        for (int num : nums) {
            preSum += num;
            // 从下标0到当前位置前缀和为preSum
            // 若当前找到了preSum - k
            // 说明从0到当前位置分成了两部分：preSum - k 和 k
            if (mp.containsKey(preSum - k)) {
                res += mp.get(preSum - k);
            }
            mp.put(preSum, mp.getOrDefault(preSum, 0) + 1);
        }
        return res;
    }
}

5 矩阵

5.1 73.矩阵置零🟡

题目：给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

链接：73. 矩阵置零

示例 ：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

思路：

比较直观的是用两个数组，分别记录哪些行和哪些列应该置0，然后根据结果将对应的行和列置0

可以使用数组的第一行和第一列代替上面的两个数组，但是要额外用两个变量记录下第一行和第一列是否有0

代码：

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean flagCol0 = false, flagRow0 = false;
        // 第一行或第一列是否有0
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                flagCol0 = true;
            }
        }
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                flagRow0 = true;
            }
        }
        // 标记该行和该列是否有0
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        // 如果当前元素所在行或所在列有0，则将当前位置置0
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        // 将第一行和第一列置0
        if (flagCol0) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
        if (flagRow0) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
    }
}

6 链表

6.1 23-160.相交链表🟢

题目：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

链接：160. 相交链表

示例 ：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

思路：

因为两个链表长度可能不一致，所以同时遍历可能无法到达相交节点。

可以先算出哪个链表较长，让其向后移动两个链表长度的差值，这样两个指针同时遍历就可以同时到达相交节点

上面思路简单但代码比较多。若遍历完当前链表再遍历另一个链表，这样也会同时到达相交节点，或者同时指向 null

如上图中，pA 走了2+3+3到了节点8，pB 走了3+3+2同样到了节点8

代码：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            // pA走到末尾转到B链表，PB走到末尾转到A链表
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

6.2 24-206.反转链表🟢🔥

题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

链接：206. 反转链表

示例 ：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

思路：

用一个指针 cur 用来遍历单链表，再用另一个指针 prev 指向 cur 的前面一个节点。例如 cur=2时，原本是1->2，现在要变成2->1。直接让 cur->next=pre 就可以实现，但这样的话，后面的3就没法遍历到了。所以要用一个临时指针 tmp 先指向 cur->next，再让 cur->next=pre。

到这里，就实现了1和2的反转，如果想继续遍历下去，只需让 pre 和 cur 都向后移一位。

代码：

1.迭代法(双指针)

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode pre = null, next = null;
        while (cur != null) {
            next = cur.next; // 更新 next
            cur.next = pre; // 反转操作
            pre = cur; // 更新 pre
            cur = next; // 更新 cur
        }
        return pre;
    }
}

2.递归(也要会)

class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(head, null);
    }

    public ListNode reverse(ListNode cur, ListNode pre) {
        if (cur == null) {
            return pre;
        }
        ListNode next = cur.next;
        cur.next = pre;
        return reverse(next, cur);
    }
}

6.3 92.反转链表 II(扩展)🟡

题目：给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

链接：92. 反转链表 II

示例 ：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

思路：

• 首先根据 left 找到待反转链表的位置
• 然后利用反转链表的逻辑将待反转链表反转后
• 再把反转后的链表和前后区间的链表相连即可。

代码：

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(0, head), p0 = dummy;
        for (int i = 0; i < left - 1; ++i) {
            p0 = p0.next; // 指向待反转链表的前一个节点
        }

        ListNode cur = p0.next;
        ListNode pre = null, next = null;
        // 反转之后 pre 是反转区间新的头节点，cur 是下个区间的 head
        for (int i = 0; i < right - left + 1; ++i) {
            // 和反转链表题目一样的逻辑
            next = cur.next;
            cur.next = pre; // 执行right - left + 1次反转操作
            pre = cur;
            cur = next;
        }

        // tail是反转后区间的末尾，指向下个区间的head
        ListNode tail = p0.next;
        tail.next = cur;
        // 反转区间的前一个节点指向反转区间新的头节点
        p0.next = pre;
        return dummy.next;
    }
}

6.4 25.K 个一组翻转链表🔴🔥

题目：给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

链接：25. K 个一组翻转链表

示例 ：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

思路：

和反转链表 II 类似，只不过要反转多个区间。

• 首先统计节点个数来确定要进行多少个区间的反转操作
• 然后利用反转链表的逻辑将待反转链表反转后
• 再把反转后的链表和前后区间的链表相连，同时更新待反转区间的前一个节点 p0，循环下一个区间的反转操作。

视频讲解：反转链表_哔哩哔哩_bilibili

代码：

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 统计节点个数
        ListNode dummy = new ListNode(-1, head), p0 = dummy;
        int n = 0;
        ListNode cur = head;
        while (cur != null) {
            n++;
            cur = cur.next;
        }

        cur = head;
        ListNode pre = null, next = null;
        while (n >= k) {
            n -= k;
            // 翻转之后 pre 是反转区间新的头节点，cur 是下个区间的 head
            for (int i = 0; i < k; ++i) {
                // 和反转链表一样的逻辑
                next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }

            // tail是反转后区间的末尾，指向下个区间的head
            ListNode tail = p0.next;
            tail.next = cur;
            // 反转区间的前一个节点指向反转区间新的头节点
            p0.next = pre;
            // p0来到当前区间的末尾，也就是后一个区间的前一个节点
            p0 = tail;
        }
        return dummy.next;
    }
}

6.5 25-234.回文链表🟢

题目：给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

链接：234. 回文链表

示例 ：

输入：head = [1,2,2,1]
输出：true

进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

思路：

因为单链表没法从后向前遍历，所以没法用左右双指针遍历判断。但可以先把值放到一个数组中，这样就可以用左右指针向中间遍历来判断。

为了优化空间，可以先找到链表的中间位置，将后面的链表反转。用两个指针分别指向前半部分的链表和后半部分的链表，从而避免创建数组。

代码：

1.值复制到数组然后双指针

class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> list = new ArrayList<>();
        ListNode cur = head;
        while (cur != null) {
            list.add(cur.val);
            cur = cur.next;
        }
        // 问题变为判断数组中的元素是否是回文
        int left = 0, right = list.size() - 1;
        while (left < right) {
            if (!list.get(left).equals(list.get(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

2.快慢指针

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow, fast;
        slow = fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 链表长度为奇数，slow向后一步左右两边子链表长度一致
        if (fast != null)
            slow = slow.next;

        ListNode left = head;
        // 后半部分反转
        ListNode right = reverse(slow);
        while (right != null) {
            if (left.val != right.val)
                return false;
            left = left.next;
            right = right.next;
        }

        return true;
    }

    ListNode reverse(ListNode head) {
        ListNode pre = null, cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
// 详细解析参见：
// https://labuladong.online/algo/slug.html?slug=palindrome-linked-list

6.6 26-141.环形链表🟢

题目：给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

链接：141. 环形链表

示例 ：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

思路：

判断有没有环，也就是判断遍历到的当前节点是否之前也遍历到过，所以可以用 HashSet 来快速判断当前节点是否在之前遍历过的节点中

也可以用快慢指针，慢指针走一步，快指针走两步。若是存在环，快指针一定会在某一节点追上慢指针

代码：

public class Solution {
    public boolean hasCycle(ListNode head) {
        // 快慢指针初始化指向 head
        ListNode slow = head, fast = head;
        // 快指针走到末尾时停止
        while (fast != null && fast.next != null) {
            // 慢指针走一步，快指针走两步
            slow = slow.next;
            fast = fast.next.next;
            // 快慢指针相遇，说明含有环
            if (slow == fast) {
                return true;
            }
        }
        // 不包含环
        return false;
    }
}

6.7 27-142.环形链表 II🟡

题目：如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

链接：142. 环形链表 II

示例 ：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

思路：

这题和上题一样，依然可以用 HashSet 快速判断当前节点是否之前遍历过，而且第一次重复的节点就是环的入口。

如果想优化空间，上题的解法快慢指针相遇的地方不一定是环的入口，如例子中会在 -4 相遇。相遇时，只需让一个 tmp 指针从 head 出发，和 slow 一样每次都是走一步，相遇的地方就是环的入口。

代码：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            // 快慢指针相遇，说明有环
            if (slow == fast) {
                // tmp从head出发，和slow相遇的节点就是入口
                ListNode tmp = head;
                while (slow != tmp) {
                    slow = slow.next;
                    tmp = tmp.next;
                }
                return slow;
            }
        }
        return null;
    }
}

6.8 28.合并两个有序链表🟢🔥

题目：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

链接：21. 合并两个有序链表

示例 ：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

思路：

两个指针分别指向两个链表，谁的节点值小下一个就用谁的，最后连接上非空的那个链表即可。为了方便操作和最终返回头结点，这里要设一个虚拟头结点

代码：

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode(-1);
        ListNode cur = dummyHead;
        while (list1 != null && list2 != null) {
            if (list1.val > list2.val) {
                cur.next = list2;
                list2 = list2.next;
            } else {
                cur.next = list1;
                list1 = list1.next;
            }
            cur = cur.next;
        }
        // 拼接把剩下的链表
        if (list1 != null) {
            cur.next = list1;
        } else {
            cur.next = list2;
        }
        return dummyHead.next;
    }
}

6.9 29-2.两数相加🟡

题目：给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

链接：2. 两数相加

示例 ：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

思路：

两数相加和平常计算两个数字相加一样，不过是遍历两条链表逐渐相加。主要是存在进位的情况，需要一个变量记录上次相加的进位。

这题需要注意的是如果用 while (l1 != null || l2 != null) 来判断会漏掉最后两个数相加有进位的情况，所以要加上 || 进位 > 0 的条件

代码：

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 在两条链表上的指针
        ListNode p1 = l1, p2 = l2;
        // 虚拟头结点（构建新链表时的常用技巧）
        ListNode dummy = new ListNode(-1);
        // 指针 p 负责构建新链表
        ListNode p = dummy;
        // 记录进位
        int carry = 0;
        // 开始执行加法，两条链表走完且没有进位时才能结束循环
        while (p1 != null || p2 != null || carry > 0) {
            // 先加上上次的进位
            int val = carry;
            if (p1 != null) {
                val += p1.val;
                p1 = p1.next;
            }
            if (p2 != null) {
                val += p2.val;
                p2 = p2.next;
            }
            // 处理进位情况
            carry = val / 10;
            val = val % 10;
            // 构建新节点
            p.next = new ListNode(val);
            p = p.next;
        }
        // 返回结果链表的头结点（去除虚拟头结点）
        return dummy.next;
    }
}

6.10 30-19.删除链表的倒数第 N 个结点🟡

题目：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

链接：19. 删除链表的倒数第 N 个结点

示例 ：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

思路：

最简单的方法就是先遍历一次链表算出链表长度，然后再遍历一次走到待删节点前一个进行删除操作。

之所以要两次遍历是无法确定 len - n 的值，那我们可以让一个指针先走 n 步，此时让另一个节点从头出发，他们俩同时向后遍历，从而确定 len - n 的值

注意可能会删除 head 节点引发空指针异常，所以要设置一个 dummy 节点

代码：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode fast = dummy, slow = dummy;
        // 因为指针初始是在dummy，所以这里多走一步
        for (int i = 0; i < n + 1; i++) {
            fast = fast.next;
        }
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

6.11 31-24.两两交换链表中的节点🟡

题目：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

链接：24. 两两交换链表中的节点

示例 ：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

思路：

链表题目都是涉及到指针移动的问题，最好在纸上画画，防止绕晕。

可以先不考虑怎么移动指针，先考虑交换两个链表节点应该怎么做。

cur.next = cur.next.next 即 1.next=3，然后我们想让 2.next=1 或者 0.next=2 的时候，会发现此时的 2 因为和 1 的连接断开了， 已经找不到了。所以就要用一个临时节点提前把 2 存起来

交换过两个节点后，现在是 0 2 1 3，cur=1,prev=0 ，按照对 cur 和 prev 的定义，下一次交换时 cur=3,prev=1，所以对应的代码就是 prev = cur;cur = cur.next;

代码：

1.迭代解法

class Solution {  
    public ListNode swapPairs(ListNode head) {  
        ListNode dummy = new ListNode(-1, head);  
        ListNode prev = dummy, cur = head;  
        // 下一个待反转的为null 或者 下一对待反转的只有1个元素  
        while (cur != null && cur.next != null) {  
            ListNode tmp = cur.next;  
            cur.next = tmp.next;  
            prev.next = next;  
            tmp.next = cur;  
  
            // 更新两个指针  
            prev = cur;  
            cur = cur.next;  
  
        }  
        return dummy.next;  
    }  
}

2.递归解法

能看懂，但下次遇到想不到，起码把迭代解法搞明白就可以了

class Solution {
    // 定义：输入以 head 开头的单链表，将这个单链表中的每两个元素翻转，
    // 返回翻转后的链表头结点
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode first = head;
        ListNode second = head.next;
        ListNode others = head.next.next;
        // 先把前两个元素翻转
        second.next = first;
        // 利用递归定义，将剩下的链表节点两两翻转，接到后面
        first.next = swapPairs(others);
        // 现在整个链表都成功翻转了，返回新的头结点
        return second;
    }
}

6.12 146.LRU 缓存🟡🔥

题目：请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

链接：146. LRU 缓存

示例 ：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

思路：

get 和 put 要求 O(1)，那显然是 HashMap，但没有先后顺序，所以可以使用哈希链表 LinkedHashMap。

不过面试时一般要求不能直接使用 LinkedHashMap，要根据哈希表和双向链表来实现。主要就是哈希表存放 key 和对应的节点，节点之间组成双向链表的结构，节点内部存放 key 和 value 。

代码：

1.LinkedHashMap解法

class LRUCache extends LinkedHashMap<Integer, Integer>{
    private int capacity;
	
	// 设置为true表明基于访问顺序
    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

	// 调用put()方法时是否移除键值对，前面设为true表明移除最早访问的
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity; 
    }
}

2.哈希表+双向链表解法（面试要求）

class LRUCache {
    private static class Node {
        int key, value;
        Node prev, next;

        Node(int k, int v) {
            key = k;
            value = v;
        }
    }

    private final int capacity;
    private final Node dummy = new Node(0, 0); // 哨兵节点
    private final Map<Integer, Node> keyToNode = new HashMap<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
        dummy.prev = dummy;
        dummy.next = dummy;
    }

    public int get(int key) {
        Node node = getNode(key);
        return node != null ? node.value : -1;
    }

    public void put(int key, int value) {
        Node node = getNode(key);
        if (node != null) { // 有这本书
            node.value = value; // 更新 value
            return;
        }
        node = new Node(key, value); // 新书
        keyToNode.put(key, node); // 哈希表也新建一个记录
        pushFront(node); // 放在最上面
        if (keyToNode.size() > capacity) { // 书太多了
            Node backNode = dummy.prev;
            keyToNode.remove(backNode.key); // 删除哈希表的记录
            remove(backNode); // 去掉最后一本书
        }
    }

    private Node getNode(int key) {
        if (!keyToNode.containsKey(key)) { // 没有这本书
            return null;
        }
        Node node = keyToNode.get(key); // 有这本书
        remove(node); // 把这本书抽出来
        pushFront(node); // 放在最上面
        return node;
    }

    // 删除一个节点（抽出一本书）
    private void remove(Node x) {
        x.prev.next = x.next;
        x.next.prev = x.prev;
    }

    // 在链表头添加一个节点（把一本书放在最上面）
    private void pushFront(Node x) {
        x.prev = dummy;
        x.next = dummy.next;
        x.prev.next = x;
        x.next.prev = x;
    }
}

7 二叉树

7.1 102.二叉树的层序遍历🟡

题目：给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

链接：102. 二叉树的层序遍历

示例 ：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

思路：

二叉树没法很好的一层一层直接遍历，一层一层想象成一个队列放一层，然后所有队列连接起来，从前往后就是层序遍历。

关键是怎么从上一层元素获取到下一层元素，遍历上一层的时候，把当前元素放到 level 中，顺便把他的左右子节点放到队列中，这样遍历完这一层后队列存的刚好就是下一层的元素。

代码：

class Solution {  
    public List<List<Integer>> levelOrder(TreeNode root) {  
        List<List<Integer>> res = new LinkedList<>();  
        if (root == null) {  
            return res;  
        }  
  
        Queue<TreeNode> q = new LinkedList<>();  
        q.offer(root);  
        // while 循环控制从上向下一层层遍历  
        while (!q.isEmpty()) {  
            int len = q.size();  // for循环中q.size()会变，所以先存起来
            // 记录这一层的节点值  
            List<Integer> level = new LinkedList<>();  
            // for 循环控制每一层从左向右遍历  
            for (int i = 0; i < len; i++) {  
                TreeNode cur = q.poll();  
                level.add(cur.val);  
                if (cur.left != null)  
                    q.offer(cur.left);  
                if (cur.right != null)  
                    q.offer(cur.right);  
            }  
            res.add(level);  
        }  
        return res;  
    }  
}

7.2 236.二叉树的最近公共祖先🟡

题目：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

链接：236. 二叉树的最近公共祖先

示例 ：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

思路：

二叉树搜索题目，使用递归解决。如果遇到了 null 或 p 或 q 则应该 return。分别往左子树和右子树去查找最近公共祖先。然后结果一层层向上 return。

最终对于 root ，它的左右两个子树返回了查找到的结果。左子树没查到，说明结果在右子树中；右子树没查找，说明结果在左子树中；左右子树都查到，那 root 就是最近公共祖先。

代码：

class Solution {
    // 函数功能： 1.p q都能找到 返回最近公共祖先 2. p q找到一个，返回p q 3. 都没找到 返回null
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 如果根节点为空，或者根节点是p或q中的一个，直接返回根节点的值
        if (root == null || root == p || root == q) {
            return root;
        }
        // 在左子树中查找最近公共祖先
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        // 在右子树中查找最近公共祖先
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 如果左子树为空，说明p和q都不在左子树中，返回右子树的结果
        if (left == null) {
            return right;
        }
        // 如果右子树为空，说明p和q都不在右子树中，返回左子树的结果
        if (right == null) {
            return left;
        }
        // 如果左子树和右子树都返回了节点，说明p和q分别在root的两侧，root即为最近公共祖先
        return root;
    }
}

8 图论

8.1 200. 岛屿数量🟡

题目：给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

链接：200. 岛屿数量

示例 ：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

思路：

遍历二维网格，遇到陆地时，同时将其和相邻的陆地用 dfs 都淹没掉（置为 0）。这样一次遍历遇到的 1 的数量就是所有岛屿的数量。

二维矩阵的 DFS 和二叉树的遍历类似

代码：

class Solution {
    // 主函数，计算岛屿数量
    public int numIslands(char[][] grid) {
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    res++; // 每发现一个岛屿，岛屿数量加一
                    dfs(grid, i, j); // 然后使用 dfs 将其相邻的岛屿淹了
                }
            }
        }
        return res;
    }

    // 从 (i, j) 开始，将与之相邻的陆地都变成海水
    void dfs(char[][] grid, int i, int j) {
        // 超出索引边界
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) {
            return;
        }
        // 已经是海水了
        if (grid[i][j] == '0') {
            return;
        }
        // 将 (i, j) 变成海水
        grid[i][j] = '0';
        // 淹没上下左右的陆地
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }
}

9 回溯

9.1 46.全排列🟡

题目：给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

链接：46. 全排列

示例 ：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

思路：

当路径 path 个数为 nums 时添加到 res，但注意要 new 一个 path，不然加的是 path 的引用，后面 path 的改变会影响到 res

排列问题可以往前选，所以循环从 0 开始，但从 0 开始，排列选出的元素又不能重复，所以要用 used 数组来判断之前选过了没。

代码：

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> permute(int[] nums) {
        boolean[] used = new boolean[nums.length];
        backtrack(nums, used);
        return res;
    }

    private void backtrack(int[] nums, boolean[] used) {
        // 到达叶子节点
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        // 注意从0开始，可以往回选
        // [1,2]中可以选择[1,2]也可以是[2,1]
        for (int i = 0; i < nums.length; i++) {
            // 因为从0开始，所以会重复选择元素，用used去重
            if (used[i])
                continue;
            path.add(nums[i]);
            used[i] = true;
            backtrack(nums, used);
            path.removeLast();
            used[i] = false;
        }
    }
}

10 二分查找

10.1 35. 搜索插入位置🟢

题目：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

链接：35. 搜索插入位置

示例 ：

输入: nums = [1,3,5,6], target = 2
输出: 1

思路：

有序数组找位置显然是用二分查找。我个人习惯是用闭区间，所以注意 while 循环中 left==right 时也是有效循环，不然不就漏掉 left==right 的情况了吗

至于为什么最后没找到返回的是 left。下次遇到这种情况直接举个例子试试。

如 target=2，现在找到了 1 3，left=0,right=1，那 mid=0。target>nums[mid]，所以 left=right=mid=1。此时 target<nums[mid]，所以 right=0,left=1，所以 left=1 便是要插入的位置。

代码：

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        // 闭区间，所以left=right也是有效值
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (target == nums[mid]) {
                return mid;
            } else if (target > nums[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

10.2 33. 搜索旋转排序数组🟡

题目：整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

链接：33. 搜索旋转排序数组

示例 ：

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

思路：

若不考虑时间复杂度，遍历一遍挨个比较就行。时间复杂度为 O(log n) ，那还是要用二分。但由于并不是有序，不能直接用。

可以注意到 mid 分成的两边，肯定有一边是有序的；如果 target 刚好也在这个有序的中间，那可以用二分查找，否则就去另一边继续划分；另一边划分后，肯定也有一边是有序的。

代码：

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            // 左半有序 注意带等于号 对应 l=mid r=l+1
            if (nums[l] <= nums[mid]) {
                // target在左半区间内
                if (nums[l] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                // 右半有序，且target在右半区间内
                if (nums[mid] < target && target <= nums[r]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
}

11 栈

11.1 20.有效的括号🟢

题目：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

链接：20. 有效的括号

示例 ：

输入：s = "([}}])"
输出：false

思路：

括号问题就用栈做。遇到左括号就入栈，遇到右括号就和栈顶元素比较下。如果当前都不是有效的左右括号，那肯定不是有效括号，可直接输出 false。如果当前是有效左右括号，就弹出栈顶的左括号。

代码：

class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }

        Map<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put(']', '[');
        map.put('}', '{');
        Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            // 不是右括号就push
            if (map.containsKey(ch)) {
                // 栈空了或者当前右括号和栈顶不匹配 可判断是无效括号
                if (stack.isEmpty() || stack.peek() != map.get(ch)) {
                    return false;
                }
                // 当前是有效括号，pop左括号
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}

12 堆

12.1 215.数组中的第 K 个最大元素🟡🔥

题目：给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

链接：215. 数组中的第K个最大元素

示例 ：

输入: [3,2,1,5,6,4], k = 2
输出: 5

思路：

要求的是第 k 个最大，可以用堆来实现。用最小堆找出前 k 个最大，这样堆顶就是第 k 个最大。

代码：

1.优先队列

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 默认是小顶堆，堆顶是最小元素
        Queue<Integer> queue = new PriorityQueue<>();
        for (int num : nums) {
            // 前k个直接添加进去
            if (queue.size() < k) {
                queue.offer(num);
            } else {
                // 后面的比堆顶大再添加进去
                if (num > queue.peek()) {
                    queue.poll();
                    queue.offer(num);
                }
            }
        }
        // 堆中是前k个最大元素，堆顶是最小的那个，即第 k 个最大元素
        return queue.peek();
    }
}

2.快速选择

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int target = nums.length - k;
        // 第k大也就是下标为target的元素
        return quickSelect(nums, 0, nums.length - 1, target);
    }

    public static int partition(int[] nums, int left, int right) {
        // 随机在nums[left...right]的范围中, 选择一个数作为pivot
        swap(nums, left, (int) (Math.random() * (right - left + 1)) + left);
        int pivot = nums[left];
        int i = left + 1; // 左侧指针的初始位置
        int j = right; // 右侧指针的初始位置

        while (true) {
            // 左侧指针移动，直到找到一个大于基准值的元素
            while (i <= right && nums[i] < pivot) {
                i++;
            }
            // 右侧指针移动，直到找到一个小于基准值的元素
            while (j >= left + 1 && nums[j] > pivot) {
                j--;
            }
            // 两边已经分区好了，break
            if (i >= j) {
                break;
            }
            // 交换左右指针所指的元素
            swap(nums, i, j);
            i++;
            j--;
        }
        // j指向的是最后一个小于pivot的元素，所以和j交换
        swap(nums, left, j);
        return j;
    }

    public static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public static int quickSelect(int[] nums, int left, int right, int target) {
        if (left == right) {
            return nums[left];
        }

        int pivotIndex = partition(nums, left, right);
        if (target == pivotIndex) {
            return nums[target];
        } else if (target < pivotIndex) {
            return quickSelect(nums, left, pivotIndex - 1, target);
        } else {
            return quickSelect(nums, pivotIndex + 1, right, target);
        }
    }
}

和快速排序相比就 quickSelect 函数不同，快排函数如下

public static void quickSort(int[] nums, int left, int right) {  
    if (left >= right) {  
        return;  
    }  
    // 获取划分子数组的位置  
    int pivotIndex = partition(nums, left, right);  
    // 对左半部分进行快速排序  
    quickSort(nums, left, pivotIndex - 1);  
    // 对右半部分进行快速排序  
    quickSort(nums, pivotIndex + 1, right);  
}

12.2 347.前 K 个高频元素🟡🔥

题目：给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

链接：347. 前 K 个高频元素

示例 ：

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

思路：

前 k 个高频元素，可以先用 HashMap 统计一下每个元素对应的频率，然后问题转换为求前 k 个最大元素。

与第 k 个最大元素不同，可以直接用大顶堆，把所有元素都添加进去，最终堆里的元素就是前 k 个最大元素。不过这样每个元素都要过一遍堆，可以用小顶堆优化下，不用把每个元素都过一遍导致每次都调整堆

注意代码中队列怎么存放 Map，以及怎么定义 Map 类型的小顶堆

代码：

1.大顶堆

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        // 小顶堆
        Queue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>
        ((a, b) -> a.getValue() - (b.getValue()));
        for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
            if (pq.size() < k) {
                pq.offer(entry);
            } else {
                if (entry.getValue() > pq.peek().getValue()) {
                    pq.poll();
                    pq.offer(entry);
                }
            }
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = pq.poll().getKey();
        }
        return res;
    }
}

13 贪心算法

13.1 121.买卖股票的最佳时机🟢

题目：给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

链接：121. 买卖股票的最佳时机

示例 ：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

思路：

想赚钱，那肯定是低价买入，高价抛出。所以用一个 minPrice 记录最小价格，向后遍历时计算当前价格减 minPrice 得到当前要是抛出赚的钱，求其中的最大值即可。

代码：

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = prices[0], res = 0;
        for (int i = 1; i < prices.length; i++) {
	        // 更新价格最小值
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            } else if (prices[i] - minPrice > res) {
	            // 计算利润最大值
                res = prices[i] - minPrice;
            }
        }
        return res;
    }
}

14 动态规划

14.1 70. 爬楼梯🟢

题目：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

链接：70. 爬楼梯

示例 ：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

思路：

后面节点的状态可以由前面的推导出来，所以要用动态规划。设 dp[n] 为 n 阶时的方法个数，那它其实就等于先爬一步，后面有 dp[i-1] 种方法 + 先爬两步，后面有 dp[i-2] 种方法

代码：

class Solution {
    public int climbStairs(int n) {
        if (n <= 2)
            return n;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            // 先爬一步，后面有dp[i-1]种方法
            // 先爬两步，后面有dp[i-2]种方法
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

14.2 118.杨辉三角🟢

题目：给定一个非负整数 numRows ，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

链接：118. 杨辉三角

示例 ：

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

思路：

下一行的结果可以由前一行的结果推导出来，并且能看出每一行的第一个和最后一个都是 1。对于非首末元素的值就等于左上角和右上角的和，直接看图可能不直观，可以把杨辉三角旋转一下，如下

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

这样就很明显能看出推导公式为dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]

代码：

class Solution {
    public List<List<Integer>> generate(int numRows) {
        // 初始化动态规划数组
        Integer[][] dp = new Integer[numRows][];
        // 遍历每一行
        for (int i = 0; i < numRows; i++) {
            // 注意：初始化当前行
            dp[i] = new Integer[i + 1];
            // 每一行的第一个和最后一个元素总是 1
            dp[i][0] = dp[i][i] = 1;
            // 计算中间元素
            for (int j = 1; j < i; j++) {
                // 中间元素等于上一行的相邻两个元素之和
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            }
        }

        // 将动态规划数组转换为结果列表
        List<List<Integer>> res = new ArrayList<>();
        for (Integer[] row : dp) {
            res.add(Arrays.asList(row));
        }
        // 返回结果列表
        return res;
    }
}

14.3 198.打家劫舍🟡

题目：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

链接：198. 打家劫舍

示例 ：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

思路：

只有一间屋时没得选，dp[0] = nums[0]。两间屋时，选最大的那个。之后对于每个位置有两种选择，偷还是不偷当前位置，从中选择最大的那个。

• 要是偷当前位置，这样就不能偷前一个，此时和为 dp[i - 2] + nums[i]
• 若是不偷当前位置，那和就与前一个位置相同，dp[i - 1]

代码：

class Solution {
    public int rob(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int[] dp = new int[length];
        dp[0] = nums[0]; // 只有1间屋
        dp[1] = Math.max(nums[0], nums[1]); // 两间屋选最大的那个
        for (int i = 2; i < length; i++) {
            // 偷当前位置 和 不偷当前位置 取最大
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[length - 1];
    }
}

因为结果只和前两间房屋的最高金额有关，没必要记录所有位置的最高金额，可以用两个变量代替数组

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int first = nums[0], second = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }
}

扩展：213. 打家劫舍 II：这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。

代码：

class Solution {
    public int rob(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        } else if (length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        // 偷第1家 和 不偷第1家取最大
        return Math.max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));
    }

    public int robRange(int[] nums, int start, int end) {
        int first = nums[start], second = Math.max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }
}

14.4 300. 最长递增子序列 🟡

题目：给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列

链接：300. 最长递增子序列

示例 ：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

思路：

当前位置的结果能由前面的元素的结果推导出来，所以可以用动态规划。

但如果 dp[i] 表示的是最终结果，不选的话直接用前一个的结果，但选的话还要满足递增，那比前面的哪个大算递增呢。如果从前往后一个个比较，但当前位置比前面的大，不代表直接能用前面的结果加1。因为前面的结果可能是前面那个位置的元素没有选的结果。如 1，5，9，4，6，dp[3]=3 时4就没有选， dp[4]!=dp[3]+1

关键点在于我们无法确定前面的 dp[i] 的结果中 nums[i] 有没有选，那我们可以把 dp[i] 定义成 nums[i] 一定被选时的结果，然后求出所有的 dp[i] 的最大值就是最终结果。

代码：

class Solution {
    public int lengthOfLIS(int[] nums) {
        // dp数组表示0..i时的结果，且nums[i]必须被选择
        int[] dp = new int[nums.length];
        // 初始化每个dp都是1即只选当前元素
        Arrays.fill(dp, 1);
        int res = 1; // 解决nums只有1个元素的情况，也可以下面i从0开始:res=0
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                // 因为必须选择nums[i]，所以nums[i]必须大于nums[j]才能满足递增
                if (nums[i] > nums[j]) {
                    // 对于每个j，dp[i]=dp[j]+1，求所有j中最大的dp[i]
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            // 所有dp里面的最大值就是res
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

15 多维动态规划

15.1 1143.最长公共子序列🟡

题目：给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

链接：1143. 最长公共子序列

示例 ：

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

思路：

最长公共子序列是典型的二维动态规划问题，后面的状态可以由前面的状态推出。

当两个指针指向的两个字符串的字符相同时，那当前长度就等于两个指针都向前退一位后的长度加1。

若不等，要么 text1 退1位，要么 text2 退1位，求两者最大。

注意 dp 的长度要设为字符串长度+1。如果是用0表示字符串第1个位置，那就要初始化 dp[0][...] 和 dp[...][0]。但是这样要判断第1个字符是不是在另一个字符串里面，初始化比较麻烦。所以 dp[i] 代表的是 0...i-1，这样 dp[0] 就是0，不用再写初始化的代码了

代码：

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        // 定义：text1[0..i-1] 和 text2[0..j-1] 的 lcs 长度为 dp[i][j]
        int[][] dp = new int[m + 1][n + 1];
        // 目标：text1[0..m-1] 和 text2[0..n-1] 的 lcs 长度，即 dp[m][n]
        // base case: dp[0][..] = dp[..][0] = 0

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 当前两字符若相等，i 和 j 从 1 开始，所以要减一
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    // 两个字符串都去除最后一个字符的lcs长度 + 1
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } else {
                    // text2减一个字符后和text1的lcs长度 
                    // 与text1减1个字符后和text2的长度 取最大
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }

        return dp[m][n];
    }
}