1. 两数之和

哈希表

使用哈希表，可以将寻找 target - x 的时间复杂度降低到从$O(N)$降低到$O(1)$

创建一个哈希表，键为数组中的元素，值为元素的下标

对于每一个 x，我们首先查询哈希表中是否存在 target - x

• 如果存在 ，返回 target - x 对应的下标和当前 x 的下标
• 如果不存在，将 x 插入到哈希表中

JavaScript

var twoSum = function (nums, target) {
  const map = new Map()
  for (let i = 0; i < nums.length; i++) {
    if (map.has(target - nums[i])) {
      return [map.get(target - nums[i]), i]
    }
    map.set(nums[i], i)
  }
  return []
}

Java

class Solution {
public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            if(hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]),i};
            }
            hashtable.put(nums[i],i);
        }
        return new int[0];
    }
}

2. 两数相加

由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。

我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。具体而言，如果当前两个链表处相应位置的数字为$n1,n2$，进位值为 $\textit{carry}$，则它们的和为 $n1+n2+\textit{carry}$；其中，答案链表处相应位置的数字为$(n1+n2+\textit{carry}) \% 10$，而新的进位值为 $\lfloor\frac{n1+n2+\textit{carry}}{10}\rfloor$。

如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个$0$ 。

此外，如果链表遍历结束后，有$\textit{carry} > 0$，还需要在答案链表的后面附加一个节点，节点的值为 $\textit{carry}$。

JavaScript

var addTwoNumbers = function (l1, l2) {
  let head = null,
    tail = null
  let carry = 0
  while (l1 || l2) {
    const n1 = l1 ? l1.val : 0
    const n2 = l2 ? l2.val : 0
    const sum = n1 + n2 + carry
    if (!head) {
      head = tail = new ListNode(sum % 10)
    } else {
      tail.next = new ListNode(sum % 10)
      tail = tail.next
    }
    carry = Math.floor(sum / 10)
    if (l1) {
      l1 = l1.next
    }
    if (l2) {
      l2 = l2.next
    }
  }
  if (carry > 0) {
    tail.next = new ListNode(carry)
  }
  return head
}

Java

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry > 0) {
            tail.next = new ListNode(carry);
        }
        return head;
    }
}

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

滑动窗口

什么是滑动窗口？

其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

如何移动？

我们只要把队列的左边的元素移出就行了，直到满足题目要求！

一直维持这样的队列，找出队列出现最长的长度时候，求出解！

JavaScript

var lengthOfLongestSubstring = function (s) {
  const occ = new Set()
  let ans = 0,
    rk = -1
  let len = s.length
  for (let i = 0; i < len; i++) {
    if (i != 0) {
      occ.delete(s.charAt(i - 1))
    }
    while (rk + 1 < len && !occ.has(s.charAt(rk + 1))) {
      occ.add(s.charAt(rk + 1))
      rk++
    }
    ans = Math.max(ans, rk - i + 1)
  }
  return ans
}

Java

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> occ = new HashSet<Character>();
        int ans = 0, rk = -1;
        int len = s.length();
        for (int i = 0; i < len; i++) {
            if (i != 0) {
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < len && !occ.contains(s.charAt(rk + 1))) {
                occ.add(s.charAt(rk + 1));
                rk++;
            }
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }
}

4. 寻找两个正序数组的中位数

采用二分法，假设两个有序数组分别为 $\text{A}$、$\text{B}$，找到它们的中位数等同于找到它们第 $k$ 小的数为 $(m+n)/2$ 或 $(m+n)/2+1$。

由于 $\text{A}[k/2-1]$ 和 $\text{B}[k/2 - 1]$ 前面有 $\text{A}[0..k/2-2]$ 和 $\text{B}[0..k/2-2]$个元素，即 $(k/2-1)$ + $(k/2-1)$ = $k/2$，所以不是第 $k$ 个数。

所以可以比较 $\text{A}[k/2-1]$ 和 $\text{B}[k/2-1]$，有以下三种情况

可以看到比较$\text{A}[k/2 - 1]$ 和 $\text{B}[k/2 - 1]$后，排除了 $k/2$个不是第 $k$ 小的数。同时，我们将在排除后的新数组上继续进行二分查找，并且根据我们排除数的个数，减少 $k$ 的值，这是因为我们排除的数都不大于第 $k$ 小的数。

有三种边界情况需要注意

如果 $\text{A}[k/2-1]$ 或者 $\text{B}[k/2-1]$ 越界，那么我们可以选取对应数组中的最后一个元素。

如果一个数组为空，说明该数组中的所有元素都被排除，我们可以直接返回另一个数组中第 $k$ 小的元素。

如果 $k=1$，我们只要返回两个数组首元素的最小值即可。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length, length2 = nums2.length;
        int totalLength = length1 + length2;
        double median;
        if (totalLength % 2 != 0) {
            int midIndex = totalLength / 2;
            median = getKthElement(nums1, nums2, midIndex + 1);
        } else {
            int midIndex1 = totalLength / 2, midIndex2 = totalLength / 2 - 1;
            median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
        }
        return median;
    }

    public int getKthElement(int[] nums1, int[] nums2, int k) {
        int index1 = 0, index2 = 0;
        int length1 = nums1.length, length2 = nums2.length;
        int kthElement = 0;
        while (true) {
            if (index1 == length1) {
                return nums2[index2 + k - 1];
            }
            if (index2 == length2) {
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }

            int half = k / 2;
            int newIndex1 = Math.min(index1 + half, length1) - 1;
            int newIndex2 = Math.min(index2 + half, length2) - 1;
            int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            } else {
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }

    }
}

5. 最长回文子串

方法：动态规划

• 状态：$\text{dp}[i][j]$ 表示字串 $\text{s}[i..j]$ 是否为回文串

• 状态转移方程：$\text{dp}[i][j]$ $=$ $($$\text{s}[i]$ $==$ $\text{s}[j]$$)$ $and$ $\text{dp}[i + 1][j - 1]$

  边界条件：$(j - 1) - (i + 1) + 1 < 2$，整理得 $j - i < 3$

• 初始化：$\text{dp}[i][j]$ $=$ $\text{true}$

• 输出：在得到一个状态的值为 $\text{true}$ 的时候，记录起始位置和长度，填表完成以后再截取

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }
        int maxLen = 1;
        int begin = 0;

        // dp[i][j] 表示 s[i..j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        char[] charArr = s.toCharArray();
        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j; i++) {
                if (charArr[i] != charArr[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
}

10. 正则表达式匹配

方法：状态转移

• 状态$f[i][j]$表示$s$的前$i$个字符与$p$的前$j$个字符是否能匹配

• 状态转移方程：

  $$f[i][j] = \begin{cases} \text{if}(p[j] \neq '\text{*}') = \begin{cases} f[i-1][j-1] , & matches(s[i],p[j]) \\ \text{false} , & otherwise \end{cases} \\ otherwise = \begin{cases} f[i-1][j] \text{or} f[i][j-2] , & matches(s[i],p[j-1]) \\ f[i][j-2] , & otherwise \end{cases}\end{cases}$$

• 边界条件：$f[0][0] = \text{true}$

• 输出：$f[m][n]$

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();

        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    f[i][j] = f[i][j - 2];
                    if (matches(s, p, i, j - 1)) {
                        f[i][j] = f[i][j] || f[i - 1][j];
                    }
                } else {
                    if (matches(s, p, i, j)) {
                        f[i][j] = f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[m][n];
    }

    public boolean matches(String s, String p, int i, int j) {
        if (i == 0) {
            return false;
        }
        if (p.charAt(j - 1) == '.') {
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }
}

11. 盛最多水的容器

方法：双指针

两个指针$left$和$right$分别指向头尾两个数，移动较小的数，遇到比自身大的数时，计算面积，比较左右指针所指的数的大小，再次移动较小的数。

class Solution {
    public int maxArea(int[] height) {
        int len = height.length;
        int left = 0, right = len - 1;
        int maxarea = Math.min(height[left], height[right]) * (right - left);
        boolean leftRun = height[left] < height[right];
        while (left < right) {
            if (leftRun) {
                int newLeft = left;
                do {
                    newLeft++;
                    if (height[left] < height[newLeft]) {
                        left = newLeft;
                        int low = Math.min(height[left], height[right]);
                        maxarea = Math.max(maxarea, low * (right - left));
                        leftRun = height[left] < height[right];
                        break;
                    }
                } while (newLeft < right);
                if (newLeft == right) break;
            } else {
                int newRight = right;
                do {
                    newRight--;
                    if (height[right] < height[newRight]) {
                        right = newRight;
                        int low = Math.min(height[left], height[right]);
                        maxarea = Math.max(maxarea, low * (right - left));
                        leftRun = height[left] < height[right];
                        break;
                    }
                } while (left < newRight);
                if (newRight == left) break;
            }
        }
        return maxarea;
    }
}

15. 三数之和

排序 + 双指针

首先固定一个数，这样问题就转化成了求解两数之和，然后使用双指针求解，首先要将数组进行排序，遍历排序后数组：

• 若 $nums[i] > 0$：因为已经排序好，所以后面不可能有三个数加和等于 $0$，直接返回结果。

• 对于重复元素：跳过，避免出现重复解

• 令左指针 $L=i+1$，右指针 $R=n-1$，当 $L<R$ 时，执行循环：

  • 当 $nums[i]+nums[L]+nums[R]==0$，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 $L,R$ 移到下一位置，寻找新的解

  • 若和大于 $0$，说明 $nums[R]$ 太大，$R$ 左移

  • 若和小于 $0$，说明 $nums[L]$ 太小，$L$ 右移

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length <= 2) return ans;

        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) break; // 第一个数大于 0，后面的数都比它大，肯定不成立了
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 去掉重复情况
            int target = -nums[i];
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                if (nums[left] + nums[right] == target) {
                    ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));

                    // 现在要增加 left，减小 right
                    left++;
                    right--; // 首先无论如何先要进行加减操作
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                } else if (nums[left] + nums[right] < target) {
                    left++;
                } else {  // nums[left] + nums[right] > target
                    right--;
                }
            }
        }
        return ans;
    }
}

17. 电话号码的字母组合

首先使用哈希表存储每个数字对应的所有可能的字母，然后进行回溯操作。

回溯过程中维护一个字符串，表示已有的字母排列（如果未遍历完电话号码的所有数字，则已有的字母排列是不完整的）。该字符串初始为空。每次取电话号码的一位数字，从哈希表中获得该数字对应的所有可能的字母，并将其中的一个字母插入到已有的字母排列后面，然后继续处理电话号码的后一位数字，直到处理完电话号码中的所有数字，即得到一个完整的字母排列。然后进行回退操作，遍历其余的字母排列。

回溯算法用于寻找所有的可行解，如果发现一个解不可行，则会舍弃不可行的解。在这道题中，由于每个数字对应的每个字母都可能进入字母组合，因此不存在不可行的解，直接穷举所有的解即可。

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> combinations = new ArrayList<String>();
        if (digits.length() == 0) {
            return combinations;
        }
        Map<Character, String> phoneMap = new HashMap<Character, String>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
        backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
        return combinations;
    }

    public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
        if (index == digits.length()) {
            combinations.add(combination.toString());
        } else {
            char digit = digits.charAt(index);
            String letters = phoneMap.get(digit);
            int lettersCount = letters.length();
            for (int i = 0; i < lettersCount; i++) {
                combination.append(letters.charAt(i));
                backtrack(combinations, phoneMap, digits, index + 1, combination);
                combination.deleteCharAt(index);
            }
        }
    }
}

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

先遍历一边链表，将链表的每个节点都存入 ArrayList，然后取出要删除节点的前一个节点进行删除操作。

tip：一般添加一个哑节点(dummy node)，它的$\textit{next}$指针指向头节点。这样一来，我们就不需要对头节点进行特殊的判断了。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        List<ListNode> nodeList = new ArrayList<ListNode>();
        ListNode p = head;
        while (p != null) {
            nodeList.add(p);
            p = p.next;
        }
        if (nodeList.size() == 1) {
            return null;
        }
        if (n == nodeList.size()) {
            return head.next;
        }
        p = nodeList.get(nodeList.size() - n - 1);
        p.next = p.next.next;
        return head;
    }
}

20. 有效的括号

用栈实现，用循环首先是否为( { [,是的话就压入栈，再判断是否为) } ]是的话就看与出栈的元素是否匹配，最后如果 arr 为空，就说明括号有效

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

        Map<Character, Character> pairs = new HashMap<Character, Character>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Deque<Character> stack = new LinkedList<Character>();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (pairs.containsKey(ch)) {
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}

21. 合并两个有序链表

逐个比较两链表节点，比较大小,用另一个链表存储节点

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode res = head;
        while (l1 != null && l2 != null) {
            if (l1.val > l2.val) {
                head.next = l2;
                l2 = l2.next;
            } else {
                head.next = l1;
                l1 = l1.next;
            }
            head = head.next;
        }
        if (l1 != null) {
            head.next = l1;
        }
        if (l2 != null) {
            head.next = l2;
        }
        return res.next;
    }
}

22. 括号生成

回溯算法(深度优先遍历)

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<String>();
        backtrack(ans, new StringBuilder(), 0, 0, n);
        return ans;
    }

    public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
        if (cur.length() == max * 2) {
            ans.add(cur.toString());
            return;
        }
        if (open < max) {
            cur.append("(");
            backtrack(ans, cur, open + 1, close, max);
            cur.deleteCharAt(cur.length() - 1);
        }

        if (close < open) {
            cur.append(")");
            backtrack(ans, cur, open, close + 1, max);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}

23. 合并 K 个升序列表

分治合并 将 k 个链表两两一组分别合并，不断重复，最终得到有序列表

注意 配对的时候不是顺序的依次配对 而是从类似于二分查找一样的从中间分,最后找到两个链表合并

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode res = head;
        while (l1 != null && l2 != null) {
            if (l1.val > l2.val) {
                head.next = l2;
                l2 = l2.next;
            } else {
                head.next = l1;
                l1 = l1.next;
            }
            head = head.next;
        }
        if (l1 != null) {
            head.next = l1;
        }
        if (l2 != null) {
            head.next = l2;
        }
        return res.next;
    }

    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r) {
            return lists[l];
        }
        if (l > r) {
            return null;
        }

        int mid = (l + r) / 2;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

}

31. 下一个排列

如何得到一个紧邻的下一个排列？

1. 首先我们要希望下一个数要比当前这个数大，所以我们只需要将后面的大数与前面的小数交换。比如 123456，将 5 和 6 交换就能得到一个更大的数 123465。
2. 我们还希望下一个数增加的幅度尽可能小，这样才能得到紧邻的下一个数。为了满足这个要求，我们需要：
   1. 尽可能的交换靠右的低位，所以需要从后往前遍历
   2. 将尽可能小的大数与前面的小数交换。比如 123465，下一个排列应该把 5 和 4 交换而不是把 6 和 4 交换
   3. 将大数换到前面后，需要将大数后面的数重置为升序排列。以 123465 为例：首先按照上一步，交换 5 和 4，得到 123564；然后需要将 5 之后的数重置为升序，得到 123546。显然 123546 比 123564 更小，123546 就是 123465 的下一个排列

算法实现上来说

1. 首先从后往前遍历，找到第一组相邻的升序元素对(i,j)，A[i] < A[j]。此时[j,end)一定是降序。
2. 在 [j,end) 从后向前查找第一个满足 A[i] < A[k] 的 k。A[i]、A[k] 分别就是上文所说的「小数」、「大数」
3. 将 A[i] 与 A[k] 交换
4. 可以断定这时 [j,end) 必然是降序，逆置 [j,end)，使其升序
5. 如果在步骤 1 找不到符合的相邻元素对，说明当前 [begin,end) 为一个降序顺序，则直接跳到步骤 4

class Solution {
    public void nextPermutation(int[] nums) {
        int length = nums.length;
        int i, j, k = 0;
        for (i = length - 1; i > 0; i--) {
            if (nums[i] > nums[i - 1]) {
                k = i;
                for (j = length - 1; j >= k; j--) {
                    if (nums[j] > nums[k - 1]) {
                        int temp = nums[j];
                        nums[j] = nums[k - 1];
                        nums[k - 1] = temp;
                        break;
                    }
                }

                break;
            }
        }
        for (i = k, j = length - 1; i < j; i++, j--) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
}

32. 最长有效括号

动态规划

定义dp[i]为以下标 i 的字符结尾的最长有效括号的长度。

对于dp[i]有两种情况：

• 如果s[i]为(:

  s[i]无法和其之前的元素组成有效的括号对，dp[i] = 0,可以直接忽略

• 如果s[i]为):

  此时我们需要对元素来判断是否有有效括号对。

  通过比较和下标为 i 的元素配对的下标为i - dp[i-1] - 1的元素 与当前的右括号相匹配的左括号位置：前面有效括号长度再往前一个位置

  如果s[i - dp[i-1] - 1]为'(' : 则有：$dp[i] = dp[i-1] + 2$

  注意 此时，需要再往前看下，是否还有有效长度，如果有，合并过来

  例如："()(()())" 当前在计算最后一个位置时，dp[7]已经等于 dp[6]+2 = 4+2

  但需要再往前看一眼，dp[1]还有有效长度，合并过来 dp[7] = 4+2+2

  那是否还需要再往前看？

  不需要了，因为，如果前面还有有效长度，其长度肯定已经合并到 dp[2]上了

  因此，每次只需要再往前多看一眼就可以

class Solution {
    public static int longestValidParentheses(String s) {
        int length = s.length();
        if (length < 2) return 0;

        int[] dp = new int[length];
        int ans = 0;

        for (int i = 1; i < length; i++) {
            if (s.charAt(i) == ')') {
                int preLen = dp[i - 1];
                int pre = i - preLen - 1; // 寻找与当前的右括号相匹配的左括号位置：前面有效括号长度再往前一个位置
                if (pre >= 0 && s.charAt(pre) == '(') {
                    dp[i] = dp[i - 1] + 2;
                    if (pre - 1 >= 0) {
                        dp[i] += dp[pre - 1];
                    }
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}

33. 搜索旋转排序数组

二分查找

虽然数组不是完全有序的，但是当我们将数组从中间分开的时候，会出现一部分有序，一部分可能有序的情况。

对于有序的部分我们任然可以使用二分查找：

• 如果 [l,mid] 是有序数组，且 target 满足 [nums[l],nums[mid]] ，我们应该将搜索范围缩小到 [l,mid-1] ，否则在 [mid+1,r] 中寻找
• 如果 [mid+1,r] 是有序数组，且 target 满足 [nums[mid+1],nums[r]] ，我们应该将搜索范围缩小到 [mid+1,r] ，否则在 [l,mid-1] 中寻找

需要注意的是 判断左右那部分是有序的时候，可以直接比较 nums[l] 和 nums[target] 或者是 nums[r] 和 nums[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) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[l] <= nums[mid]) {
                if (nums[l] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[r]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
}

34. 在排序数组中查找元素的第一个和最后一个位置

二分查找

首先使用二分查找找到一个target的位置，其余的目标值一定在其附近，再向左右循环寻找，确定`start和end的值

可以优化的是当找到一个target的位置时，我们可以选择将l或者r赋值为mid，这样可以从左右不断逼近最左或最右的target

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) {
            return new int[]{-1, -1};
        }

        int firstPosition = findFirstPosition(nums, target);
        if (firstPosition == -1) {
            return new int[]{-1, -1};
        }

        int lastPosition = findLastPosition(nums, target);
        return new int[]{firstPosition, lastPosition};
    }

    private int findFirstPosition(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 小于一定不是解
            if (nums[mid] < target) {
                // 下一轮搜索区间是 [mid + 1, right]
                left = mid + 1;
            } else if (nums[mid] == target) {
                // 下一轮搜索区间是 [left, mid]
                right = mid;
            } else {
                // nums[mid] > target，下一轮搜索区间是 [left, mid - 1]
                right = mid - 1;
            }
        }

        // 只有一个元素的情况
        if (nums[left] == target) {
            return left;
        }
        return -1;
    }

    private int findLastPosition(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] > target) {
                // 下一轮搜索区间是 [left, mid - 1]
                right = mid - 1;
            } else if (nums[mid] == target) {
                // 下一轮搜索区间是 [mid, right]
                left = mid;
            } else {
                // nums[mid] < target，下一轮搜索区间是 [mid + 1, right]
                left = mid + 1;
            }
        }
        return left;
    }
}

39. 组合总和

搜索回溯

寻找可行解的问题，都可以使用「搜索回溯」的方法来解决。

对于本题，我们首先定义一个函数dfs(target,combine,idx)表示在数组的idx位，还剩下target需要组合，已经组合的列表为combine。递归的终止条件为target <= 0 或者是数组元素被用完。

在这个函数中，每次我们可以选择跳过第idx个数，即执行函数dfs(target,combine,idx + 1)，

也可以选择不跳过第idx个数，即执行函数dfs(target,combine,idx)。

执行过程如下图

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> combine = new ArrayList<Integer>();
        dfs(candidates, target, ans, combine, 0);
        return ans;
    }

    public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {
        if (idx == candidates.length) {
            return;
        }
        if (target == 0) {
            ans.add(new ArrayList<Integer>(combine));
            return;
        }

        // 直接跳过
        dfs(candidates, target, ans, combine, idx + 1);

        // 选择当前数
        if (target - candidates[idx] >= 0) {
            combine.add(candidates[idx]);
            dfs(candidates, target - candidates[idx], ans, combine, idx);
            combine.remove(combine.size() - 1);
        }
    }
}

42. 接雨水

双指针

当指针向一个方向移动的时候：

• 如果当前位置的高度比前面高度的最高值低时，说明当前位置可以接到雨水。接到雨水的值等于高度最大值 - 当前位置的高度
• 如果当前位置的高度比前面高度的最高值高时，说明当前位置接不到雨水，更新高度最高值即可

在移动指针的时候，我们应该移动指向的位置高度较低的指针

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        int l = 0, r = len - 1;
        int lMax = 0, rMax = 0;
        int ans = 0;
        while (l < r) {
            if (height[l] < height[r]) {
                if (height[l] >= lMax) {
                    lMax = height[l];
                } else {
                    ans += lMax - height[l];
                }
                l++;
            } else {
                if (height[r] >= rMax) {
                    rMax = height[r];
                } else {
                    ans += rMax - height[r];
                }
                r--;
            }
        }
        return ans;
    }
}

46. 全排列

回溯算法

看到全部可能的解这几个关键词就想到要用回溯算法

该问题的树形结构

设计回溯算法

• dfs(nums,ans,combine), nums代表原数组，ans代表最后的结果，combine代表已经排列的数组
• 产生不同分支用循环实现
• 终止条件 combine.size() == nums.length
• 如何判断数字是否被用过，因为数组中每个数不重复，所以判断combine是否存在这个数字就可以知道是否用过了

注意别忘了回溯算法的关键操作，回溯，即给combine增加一个数后调用dfs()后，应该把combine中这个数删除。

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        int len = nums.length;
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        if (len == 0) {
            return ans;
        }
        List<Integer> combine = new ArrayList<Integer>();
        dfs(nums, ans, combine);
        return ans;
    }

    public void dfs(int[] nums, List<List<Integer>> ans, List<Integer> combine) {
        int len = nums.length;
        if (combine.size() == len) {
            ans.add(new ArrayList<Integer>(combine));
            return;
        }
        for (int num : nums) {
            if (!combine.contains(num)) {
                combine.add(num);
                dfs(nums, ans, combine);
                // 回溯
                combine.remove(combine.size() - 1);
            }
        }
    }
}

48. 旋转图像

这是一个数学问题 要将一个矩阵顺时针旋转 90⁰，只需要先沿主对角线翻转，然后再水平翻转即可

class Solution {
    public void rotate(int[][] matrix) {
        if (matrix.length <= 1 || matrix.length != matrix[0].length) {
            return;
        }
        int nums = matrix.length;
        for (int i = 0; i < nums; ++i) {
            for (int j = 0; j < nums - i; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[nums - 1 - j][nums - 1 - i];
                matrix[nums - 1 - j][nums - 1 - i] = temp;
            }
        }
        for (int i = 0; i < nums / 2; ++i) {
            for (int j = 0; j < nums; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[nums - 1 - i][j];
                matrix[nums - 1 - i][j] = temp;
            }
        }
    }
}

49. 字母异位词分组

排序

虽然字符串的排列不同，但是排序后一定是相同的，所以只需要将排序后的字符串作为 map 的键值就可以了

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

53. 最大子序和

动态规划 / 贪心算法

• 动态规划的是首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans
• 如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
• 如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
• 每次比较 sum 和 ans 的大小，将最大值置为 ans，遍历结束返回结果

class Solution {
    public int maxSubArray(int[] nums) {
        int ans = nums[0];
        int sum = 0;
        for (int num : nums) {
            if (sum > 0) {
                sum += num;
            } else {
                sum = num;
            }
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}

55. 跳跃游戏

贪心算法

对于数组的每个位置来说，可以到达的最大位置maxIndex = 当前的位置x + 最大跳跃距离nums[x]，而当一个位置在它之前的位置的可以到达的最大位置之内的话，就一定可以通过 n 步跳跃到该位置，否则就不可到达。

所以，我们可以遍历数组，实时维护maxIndex，当当前位置的最大可到达位置比之前的大时，更新maxIndex的值,最后比较maxIndex是否大于数组长度就行。

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function (nums) {
  const length = nums.length
  if (length === 1) return true
  if (nums[0] === 0) return false
  let maxIndex = nums[0]
  for (let i = 1; i < length; i++) {
    if (i <= maxIndex) {
      maxIndex = Math.max(i + nums[i], maxIndex)
    } else {
      return false
    }
  }
  return maxIndex >= length - 1
}

56. 合并区间

排序

我们首先将数组根据start升序排序来保证每个区间是连续的，接着用ans数组来保存结果。

首先将排序后的数组sorted的第一个区间放入ans中，之后的每个区间与ans的最后一个区间比较：

• 如果当前区间的curEnd小于lastEnd，说明区间不重合，直接将当前区间加入ans
• 否则区间重合，将ans的最后一个区间的end更新为curEnd和lastEnd之中较大的值

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function (intervals) {
  let ans = []
  let sorted = intervals.sort((left, right) => left[0] - right[0])
  ans.push(sorted[0])
  for (let i = 1; i < sorted.length; i++) {
    const [_, lastEnd] = ans[ans.length - 1]
    const [curStart, curEnd] = sorted[i]
    if (curStart > lastEnd) {
      ans.push(sorted[i])
    } else {
      ans[ans.length - 1][1] = Math.max(lastEnd, curEnd)
    }
  }
  return ans
}

62. 不同路径

动态规划

我们令dp[i][j] 是到达 i, j 最多路径

动态方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]

注意，对于第一行 dp[0][j]，或者第一列 dp[i][0]，由于都是在边界，所以只能为 1

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
  const f = new Array(m).fill(0).map(() => new Array(n).fill(0))
  for (let i = 0; i < m; i++) {
    f[i][0] = 1
  }
  for (let j = 0; j < n; j++) {
    f[0][j] = 1
  }
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      f[i][j] = f[i - 1][j] + f[i][j - 1]
    }
  }
  return f[m - 1][n - 1]
}

64. 最小路径和

动态规划

令dp[i][j]是到达 i，j 的最小路径和

动态方程：

• i = 0 , j = 0时，即左上角位置，dp[i][j] = grid[i][j]
• i = 0 , j != 0时，即第一行，dp[i][j] = grid[i][j - 1]
• i != 0 , j = 0时，即第一列，dp[i][j] = grid[i - 1][j]
• i != 0 , j != 0时，dp[i][j] = grid[i][j] + Math.min(grid[i][j - 1], grid[i - 1][j])

最后的结果就是dp[m - 1][n - 1]

对于本题来说，我们不需要新建一个 dp 数组，可以直接在 grid 原数组操作。

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function (grid) {
  const m = grid.length
  const n = grid[0].length
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (i === 0 && j === 0) {
        continue
      } else if (i === 0) {
        grid[0][j] = grid[0][j - 1] + grid[0][j]
      } else if (j === 0) {
        grid[i][0] = grid[i - 1][0] + grid[i][0]
      } else {
        grid[i][j] = grid[i][j] + Math.min(grid[i][j - 1], grid[i - 1][j])
      }
    }
  }
  return grid[m - 1][n - 1]
}

70. 爬楼梯

动态规划

定义dp[n]为到达第 n 阶阶梯的方法种数

因为到达第 n 阶阶梯可以从 n-1 阶或者 n-2 阶阶梯到达，所以dp[n] = dp[n - 1] + dp[n - 2]

特殊地，我们需要将dp[1] = 1 和 dp[2] = 2作为初始条件

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  const dp = []
  dp[1] = 1
  dp[2] = 2
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }
  return dp[n]
}

72. 编辑距离

动态规划

dp[i][j]代表 word1 的前 i 个字符到 word2 的前 j 个字符需要进行的最少操作次数

额外的，需要考虑全增加/全删除的情况，所以需要预留dp[i][0]和dp[0][j]的位置

如果 word1[i] == word2[j] ，即不需操作，那么直接让dp[i][j] = dp[i-1][j-1]

如果 word[i] != word2[j]，

• 插入：word1 需要在最后插入字符才行，此时可认为 word1[0:i] 已与 word2[0:j-1]匹配，因而有 dp[i][j] = dp[i][j-1] + 1
• 删除：word1 删除其最后一个字符才行，此时可认为 word1[0:i-1] 已与 word2[0:j]匹配，因而有 dp[i][j] = dp[i-1][j] + 1
• 替换：同理，此时可认为 word1[0:i-1] 已与 word2[0:j-1]匹配，因而有 dp[i][j] = dp[i-1][j-1] + 1

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
  const n1 = word1.length
  const n2 = word2.length
  const dp = new Array(n1 + 1).fill(0).map(() => new Array(n2 + 1).fill(0))
  for (let i = 1; i <= n1; i++) {
    dp[i][0] = dp[i - 1][0] + 1
  }
  for (let j = 1; j <= n2; j++) {
    dp[0][j] = dp[0][j - 1] + 1
  }
  for (let i = 1; i <= n1; i++) {
    for (let j = 1; j <= n2; j++) {
      if (word1[i - 1] !== word2[j - 1]) {
        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
      } else {
        dp[i][j] = dp[i - 1][j - 1]
      }
    }
  }
  return dp[n1][n2]
}

75. 颜色分类

双指针

用指针p交换 0，指针q交换 2，即指针 p 左边的数都为 0，指针 q 右边的数都为 2，所以i>q之后就不用判断了。

需要注意，如果当 nums[i]和指针 q 交换之后，如果nums[i]还是为0/1，那么需要回退一位来交换这个 0/1

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function (nums) {
  const swap = (a, b) => ([nums[a], nums[b]] = [nums[b], nums[a]])
  const n = nums.length
  let p = 0
  let q = n - 1
  for (let i = 0; i <= q; ++i) {
    if (nums[i] === 0) {
      swap(i, p)
      ++p
    }

    if (nums[i] === 2) {
      swap(i, q)
      --q
      if (nums[i] !== 1) {
        --i
      }
    }
  }
}

76. 最小覆盖子串

滑动窗口

自己写的代码没用 map 超时了 😥

const minWindow = (s, t) => {
  let minLen = s.length + 1
  let start = s.length // 结果子串的起始位置
  let map = {} // 存储目标字符和对应的缺失个数
  let missingType = 0 // 当前缺失的字符种类数
  for (const c of t) {
    // t为baac的话，map为{a:2,b:1,c:1}
    if (!map[c]) {
      missingType++ // 需要找齐的种类数 +1
      map[c] = 1
    } else {
      map[c]++
    }
  }
  let l = 0,
    r = 0 // 左右指针
  for (; r < s.length; r++) {
    // 主旋律扩张窗口，超出s串就结束
    let rightChar = s[r] // 获取right指向的新字符
    if (map[rightChar] !== undefined) map[rightChar]-- // 是目标字符，它的缺失个数-1
    if (map[rightChar] == 0) missingType-- // 它的缺失个数新变为0，缺失的种类数就-1
    while (missingType == 0) {
      // 当前窗口包含所有字符的前提下，尽量收缩窗口
      if (r - l + 1 < minLen) {
        // 窗口宽度如果比minLen小，就更新minLen
        minLen = r - l + 1
        start = l // 更新最小窗口的起点
      }
      let leftChar = s[l] // 左指针要右移，左指针指向的字符要被丢弃
      if (map[leftChar] !== undefined) map[leftChar]++ // 被舍弃的是目标字符，缺失个数+1
      if (map[leftChar] > 0) missingType++ // 如果缺失个数新变为>0，缺失的种类+1
      l++ // 左指针要右移 收缩窗口
    }
  }
  if (start == s.length) return ""
  return s.substring(start, start + minLen) // 根据起点和minLen截取子串
}

78. 子集

DFS 回溯

单看每个元素，都有两种选择：选入子集，或不选入子集,比如[1,2,3]，先看 1，选 1 或不选 1，都会再看 2，选 2 或不选 2，以此类推。

考察当前枚举的数，基于选它而继续，是一个递归分支；基于不选它而继续，又是一个分支。用索引index代表当前递归考察的数字nums[index]。

当index越界时，所有数字考察完，得到一个解，位于递归树的底部，把它加入解集，结束当前递归分支。

const subsets = nums => {
  const res = []

  const dfs = (index, list) => {
    if (index == nums.length) {
      // 指针越界
      res.push(list.slice()) // 加入解集
      return // 结束当前的递归
    }
    list.push(nums[index]) // 选择这个数
    dfs(index + 1, list) // 基于该选择，继续往下递归，考察下一个数
    list.pop() // 上面的递归结束，撤销该选择
    dfs(index + 1, list) // 不选这个数，继续往下递归，考察下一个数
  }

  dfs(0, [])
  return res
}

79. 单词搜索

DFS 回溯

读完题目之后，应该很容易发现需要 DFS 来做，首先我们遍历 board 数组，将每个字符作为初始条件进行 DFS

在 DFS 函数中，如果字符和 word 字符串对应，则继续比较相邻字符，否则返回false结束

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
  const DIRECTIONS = [
    [-1, 0],
    [0, -1],
    [1, 0],
    [0, 1],
  ]
  const rows = board.length
  if (rows === 0) return false
  const cols = board[0].length
  const len = word.length
  const used = new Array(rows).fill(0).map(() => new Array(cols).fill(false))
  function dfs(x, y, begin) {
    if (begin === len - 1) {
      return board[x][y] === word[begin]
    }
    if (board[x][y] === word[begin]) {
      used[x][y] = true
      for (const direction of DIRECTIONS) {
        const newX = x + direction[0]
        const newY = y + direction[1]
        if (inArea(newX, newY) && !used[newX][newY]) {
          if (dfs(newX, newY, begin + 1)) {
            return true
          }
        }
      }
      used[x][y] = false
    }
    return false
  }

  function inArea(x, y) {
    return x >= 0 && x < rows && y >= 0 && y < cols
  }

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (dfs(i, j, 0)) {
        return true
      }
    }
  }
  return false
}

DIRECTIONS数组是偏移量数组，代表位置的移动，是解二维数组的常用技巧，在本题中DIRECTIONS数组里面的子元素的顺序无关紧要