1、剑指 Offer 56 - II.数组中数字出现的次数

这道题我感觉不需要像标准答案一样用什么状态机或者位运算，我的解法更好想，还是双O(1)。

1.1 题目

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
示例 1：

输入：nums = [3,4,3,3] 输出：4

示例 2：

输入：nums = [9,1,7,9,7,9,7] 输出：1

1.2 思路

  1. 先对nums数组升序排序；
  2. 设置划窗宽度，每次下标移动划窗宽度；
  3. 注意while里的终止条件，假设1,1,1,3,3,3,4这种情况，下标只能到第一个1和第一个3，不能到最后一个元素4；
  4. 如果跳到while循环外还没有return，表明当前情况正是1,1,1,3,3,3,4这种情况，且此时下标到了第一个4，也是最后一个元素的位置，直接返回即可。

    1.3 代码

    ```java import java.util.Arrays;

class Solution { public int singleNumber(int[] nums) { Arrays.sort(nums); // 滑窗宽度 int size = 3; int i = 0; // 不判断最后一个数字 while (i < nums.length - size) { if (nums[i] != nums[i + 1]) { return nums[i]; } i += size; } // 这里判断最后一个数字 return nums[i]; } }

  1. <a name="YLKu0"></a>
  2. # 2、[剑指 Offer 17.打印从1到最大的n位数](https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/)
  3. <a name="YTldi"></a>
  4. ## 2.1 题目
  5. 输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。<br />示例 1:
  6. > 输入: n = 1 输出: [1,2,3,4,5,6,7,8,9]
  8. <a name="FnAzm"></a>
  9. ## 2.2 思路
  10. 就正常写吧。
  11. <a name="YjLg4"></a>
  12. ## 2.3 代码
  13. ```java
  14. class Solution {
  15.     public int[] printNumbers(int n) {
  16.         int maxValue = (int) Math.pow(10, n) - 1;
  17.         int[] res = new int[maxValue];
  18.         for (int i = 1; i <= maxValue; ++i) {
  19.             res[i - 1] = i;
  20.         }
  21.         return res;
  22.     }
  23. }

3、剑指 Offer 07.重建二叉树

3.1 题目

数组 - 图1

3.2 思路

这道题是已知二叉树的前序遍历和中序遍历，能唯一确定一棵二叉树。
前序遍历：根左右；
中序遍历：左根右。
可以推出以下结论：
1. 前序遍历的第一个元素即为根节点；
2. 找到根节点后，在中序遍历数组中，根节点左边的部分是左子树的组成元素，根节点右边的部分是右子树的组成元素。即将中序遍历的数组分成了左子树、根节点、右子树；
3. 根据2中序遍历划分好的左右子树，可以获取左右子树中的元素的个数，以此在前序遍历中根据个数划分左右子树。即前序遍历的数组也划分了左子树、根节点、右子树。

根据上面推论，可以通过前序遍历生成二叉树的方式复原二叉树，需要注意以下几点：
1. 在划分中序遍历数组时需要计算左右子树的元素个数，这里可以用一个map维护，key是中序遍历的元素，value是元素对应的下标。这样做的目的是，在dfs函数里划分前序遍历的左右子树时，更加方便的获取左右子树的元素数量及下标，直接从map里get即可，不需要再遍历数组了；
2. 注意递归终止条件，当树的元素只有1个时，此时直接返回这个元素对应的树节点即可；当前序和中序数组都只有两个元素，比如前序[3,9]，中序[9,3]，对应了start > end的条件，此时应返回null；
3. 前序遍历和中序遍历的数组均成功划分了左右子树后，对root.left和root.right分治，划分左右子树时下标的计算很容易出错。
递归返回条件中，start > end时返回null不要忘。

3.3 代码

  1. import java.util.HashMap;
  2. import java.util.Map;
  4. class Solution {
  5.     private int[] preorder;
  7.     private int[] inorder;
  9.     private Map<Integer, Integer> map = new HashMap<>();
  11.     public TreeNode buildTree(int[] preorder, int[] inorder) {
  12.         this.preorder = preorder;
  13.         this.inorder = inorder;
  14.         for (int i = 0; i < inorder.length; ++i) {
  15.             map.put(inorder[i], i);
  16.         }
  17.         return dfs(0, preorder.length - 1, 0, inorder.length - 1);
  18.     }
  20.     private TreeNode dfs(int preStart, int preEnd, int inStart, int inEnd) {
  21.         if (preStart == preEnd) {
  22.             return new TreeNode(preorder[preStart]);
  23.         }
  24.         if (inStart == inEnd) {
  25.             return new TreeNode(inorder[inStart]);
  26.         }
  27.         if (preStart > preEnd || inStart > inEnd) {
  28.             return null;
  29.         }
  31.         int rootIndex = map.get(preorder[preStart]);
  32.         int leftNum = rootIndex - inStart;
  33.         int inMid = inStart + leftNum + 1;
  34.         TreeNode root = new TreeNode(preorder[preStart]);
  35.         root.left = dfs(preStart + 1, preStart + leftNum, inStart, inStart + leftNum - 1);
  36.         root.right = dfs(preStart + leftNum + 1, preEnd, inMid, inEnd);
  37.         return root;
  38.     }
  39. }

4、剑指 Offer 39. 数组中出现次数超过一半的数字

todo：摩尔投票法的思想我还是没理解

4.1 题目

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
示例 1:

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

4.2 思路

本题有三种解法：

  1. hashmap记录数组出现的次数，时间复杂度O(n)，空间复杂度O(n)；
  2. 数组升序排序，返回中间位置的元素，时间复杂度O(nlgn)，空间复杂度O(1)；
  3. 摩尔投票法，时间复杂度O(n)，空间复杂度O(1)。

重点说一下摩尔投票法的思路：

  1. 初始化： 票数统计 votes = 0 ， 众数 x；
  2. 循环： 遍历数组 nums 中的每个数字 num ；
    1. 当 票数 votes 等于 0 ，则假设当前数字 num 是众数 x；
    2. 当 num = x 时，票数 votes 自增 1 ；当 num != x 时，票数 votes 自减 1 ；
  3. 返回值： 返回 x 即可。

    4.3 代码

    数组排序：
    1. class Solution {
    2.  public int majorityElement(int[] nums) {
    3.      Arrays.sort(nums);
    4.      int mid = nums.length >> 1;
    5.      return nums[mid];
    6.  }
    7. }
    摩尔投票：
    1. class Solution {
    2.  public int majorityElement(int[] nums) {
    3.      int x = 0, votes = 0;
    4.      for (int num: nums) {
    5.          if (votes == 0) {
    6.              x = num;
    7.          }
    8.          votes = num == x? votes + 1: votes - 1;
    9.      }
    10.      return x;
    11.  }
    12. }

    5、剑指 Offer 56 - I.数组中数字出现的次数

    妙啊。

    5.1 题目

    一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
    示例 1：

    输入：nums = [4,1,4,6] 输出：[1,6] 或 [6,1]

示例 2：

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

5.2 思路

由于题目要求空间复杂度是O(1)，因此排除了用Map暴力破解法。

  1. 假设只出现一次的数字为x和y，遍历nums数组，每个元素异或操作，由于数组中其他元素均出现两次，因此异或结果是x^y；
  2. 确定x和y的二进制数哪一位不同，基于此将数组num中的元素分成两拨，x和y划分到不同的两波中，然后对每一个子数组每位元素异或，最后得到的结果就是x或者y；
  3. 如何分成两个子数组？由于第一步得到了x^y的结果，结果的二进制位数为1，则代表x和y的二进制在这一位上不同，进而可以划分两个子数组同时将x和y分别放到这两个子数组中。具体做法是：用一个二进制为1的标尺m与x^y的结果按位与，如果为0，则m << 1，直到不为0，则代表此时找到了x^y为1的位数。然后用这个标尺m将数组划分为两个子数组；

  4. 注意空间复杂度为1，因此不能new两个数组然后再分别异或，而是直接遍历nums数组，将num直接与x或者y按位异或。

    5.3 代码

    1. class Solution {
    2.  public int[] singleNumbers(int[] nums) {
    3.      int val = 0;
    4.      for (int num: nums) {
    5.          val ^= num;
    6.      }
    8.      int m = 1;
    9.      while ((val & m) == 0) {
    10.          m <<= 1;
    11.      }
    12.      int x = 0, y = 0;
    13.      for (int num: nums) {
    14.          if ((num & m) == 0) {
    15.              x ^= num;
    16.          } else {
    17.              y ^= num;
    18.          }
    19.      }
    20.      return new int[]{x, y};
    21.  }
    22. }

    6、剑指 Offer 47.礼物的最大价值

    6.1 题目

    在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
    示例 1:

    输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 12 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

6.2 思路

动态规划的经典题目和入门题目，注意初始边界的赋值，需要处理dp[i][0]和dp[0][i]两个边边上的数据。

6.3 代码

  1. class Solution {
  2.     public int maxValue(int[][] grid) {
  3.         int h = grid.length;
  4.         int w = grid[0].length;
  5.         int[][] dp = new int[h][w];
  7.         // 初始值
  8.         dp[0][0] = grid[0][0];
  9.         for (int i = 1; i < h; ++i) {
  10.             dp[i][0] += dp[i - 1][0] + grid[i][0];
  11.         }
  12.         for (int i = 1; i < w; ++i) {
  13.             dp[0][i] += dp[0][i - 1] + grid[0][i];
  14.         }
  16.         // dp数组其他部分赋值
  17.         for (int i = 0; i < h - 1; ++i) {
  18.             for (int j = 0; j < w - 1; ++j) {
  19.                 dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]) + grid[i + 1][j + 1];
  20.             }
  21.         }
  22.         return dp[h - 1][w - 1];
  23.     }
  24. }

7、剑指 Offer 03.数组中重复的数字

7.1 题目

找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：

输入： [2, 3, 1, 0, 2, 5, 3] 输出：2 或 3

7.2 思路

三种思路：

  1. 用一个集合set去记录遍历了数组里哪些元素，每次遍历的时候检查当前遍历的元素是否在set中，如果在直接返回，不再继续遍历。时间复杂度O(n)，空间复杂度为O(n)；
  2. 先对数组排序，然后检查相邻的两个元素是否相等，相等则直接返回。时间复杂度O(nlgn)，空间复杂度为O(1)；
  3. 原地交换。时间复杂度O(n)，空间复杂度O(1)。这种方法还是看下题解，不好想。

    7.3 代码

    借助set：
    1. class Solution {
    2.  public int findRepeatNumber(int[] nums) {
    3.      Set<Integer> set = new HashSet<>();
    4.      for (int num: nums) {
    5.          if (set.contains(num)) {
    6.              return num;
    7.          } else {
    8.              set.add(num);
    9.          }
    10.      }
    11.      return -1;
    12.  }
    13. }
    对数组排序：
    1. class Solution {
    2.  public int findRepeatNumber(int[] nums) {
    3.      Arrays.sort(nums);
    4.      for (int i = 0; i < nums.length - 1; ++i) {
    5.          if (nums[i] == nums[i + 1]) {
    6.              return nums[i];
    7.          }
    8.      }
    9.      return -1;
    10.  }
    11. }
    原地交换：
    1. class Solution {
    2.  public int findRepeatNumber(int[] nums) {
    3.      int len = nums.length;
    4.      int i = 0;
    5.      while (i < len) {
    6.          if (nums[i] == i) {
    7.              ++i;
    8.              continue;
    9.          }
    10.          if (nums[nums[i]] == nums[i]) {
    11.              return nums[i];
    12.          }
    13.          int tmp = nums[i];
    14.          nums[i] = nums[tmp];
    15.          nums[tmp] = tmp;
    16.      }
    17.      return -1;
    18.  }
    19. }

    8、剑指 Offer 57.和为s的两个数字

    8.1 题目

    输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
    示例 1：

    输入：nums = [2,7,11,15], target = 9 输出：[2,7] 或者 [7,2]

示例 2：

输入：nums = [10,26,30,31,47,60], target = 40 输出：[10,30] 或者 [30,10]

8.2 思路

这道题如果用暴力法破解，时间复杂度为O(n2)，会有测试用例不通过。再仔细审题，数组是一个排好序的升序数组，应该利用好这一条件。
本题最佳解法是双指针，左右指针向中间收缩，由于是升序排序的数组，可以通过比较sum值和target的值，调整left和right指针来逼近。时间O(N)，空间O(1)。

8.3 代码

  1. class Solution {
  2.     public int[] twoSum(int[] nums, int target) {
  3.         int left = 0, right = nums.length - 1;
  4.         while (left < right) {
  5.             int sum = nums[left] + nums[right];
  6.             if (sum > target) {
  7.                 --right;
  8.             } else if (sum < target) {
  9.                 ++left;
  10.             } else {
  11.                 return new int[]{nums[left], nums[right]};
  12.             }
  13.         }
  14.         return new int[0];
  15.     }
  16. }

9、剑指 Offer 21.调整数组顺序使奇数位于偶数前面

双指针的思路易想，但不容易写对。

9.1 题目

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
示例：

输入：nums = [1,2,3,4] 输出：[1,3,2,4] 注：[3,1,2,4] 也是正确的答案之一。

9.2 思路

有两种思路：

  1. 用一个双向队列，然后遍历数组num，如果是奇数就放在双向队列的队首，如果是偶数就放在双向队列的队尾。这样做空间复杂度是O(n)，没有做到在数组nums上直接调整，时间复杂度为O(n)；
  2. 用双指针，左右两个指针向中间逼近，左指针找到第一个偶数，右指针直到第一个奇数，然后交换左右指针指向的值，这样做是在数组nums上直接做调整，空间复杂度为O(1)，时间复杂度为O(n)。双指针的思想不难，但是要写正确并不简单，要注意while循环的判断条件，尤其是左右指针做while循环时，虽然在外部while循环有left < right的判断，但是内部的while循环也要加上这个判断，这一点不好想。

    9.3 代码

    双向队列： ```java import java.util.LinkedList;

class Solution { public int[] exchange(int[] nums) { LinkedList list = new LinkedList<>(); for (int num: nums) { if (num % 2 == 0) { list.addLast(num); } else { list.addFirst(num); } } return list.stream().mapToInt(Integer::intValue).toArray(); } }

  1. 双指针：
  2. ```java
  3. class Solution {
  4.     public int[] exchange(int[] nums) {
  5.         int left = 0, right = nums.length - 1;
  6.         while (left < right) {
  7.             while (left < right && (nums[left] & 1) == 1) {
  8.                 ++left;
  9.             }
  10.             while (left < right && (nums[right] & 1) == 0) {
  11.                 --right;
  12.             }
  13.             int tmp = nums[left];
  14.             nums[left] = nums[right];
  15.             nums[right] = tmp;
  16.         }
  17.         return nums;
  18.     }
  19. }

10、剑指 Offer 63.股票的最大利润

10.1 题目

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
示例 1:

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

示例 2:

输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

10.2 思路

这道题有两种思路：

  1. 暴力法，两层循环求数组中后面的元素与前面的元素的最大差值。时间复杂度O(n2)，空间复杂度O(1)；
  2. 动态规划，时间复杂度O(n)，空间复杂度O(1)。

这里介绍一下动态规划的思路。

  1. 状态定义：令dp[i]表示以prices[i]结尾的子数组对应的最大利润；
  2. 转移方程：dp[i] = Math.max(dp[i - 1], prices[i] - min[0: i - 1])，其中min[0: i - 1]表示prices数组下标从0到i-1范围中最小值；
  3. 初始状态：dp[0] = 0；
  4. 返回值：dp[prices.len - 1]。

对上述基本代码做优化：

  1. 由于最后仅是返回dp[len - 1]，可以将一维的dp数组用一个值res代替，将空间复杂度由O(n)降为O(1)；
  2. 由于要求min[0: i - 1]，如果单独求需要从0到i - 1遍历，需要O(n)的时间复杂度，如果在遍历prices数组的过程中维护一个前i - 1个元素（包括第i - 1）的最小值，令这个最小值在遍历的过程中取最小，就可以借助一遍遍历数组的机会获取，而无需再单独遍历获取。

    10.3 代码

    1. class Solution {
    2.  public int maxProfit(int[] prices) {
    3.      int res = 0;
    4.      if (prices == null || prices.length == 0) {
    5.          return res;
    6.      }
    7.      int minVal = prices[0];
    8.      for (int i = 1; i < prices.length; ++i) {
    9.          minVal = Math.min(minVal, prices[i]);
    10.          res = Math.max(res, prices[i] - minVal);
    11.      }
    12.      return res;
    13.  }
    14. }

    11、剑指 Offer 31.栈的压入、弹出序列

    这道题思路是正确的，竟然写不出代码……

    11.1 题目

    输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
    示例 1：

    输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1] 输出：true 解释：我们可以按以下顺序执行： push(1), push(2), push(3), push(4), pop() -> 4, push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2：

输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2] 输出：false 解释：1 不能在 2 之前弹出。

11.2 思路

  1. 初始化一个双向队列stack，一个指向popped数组的指针index；
  2. 将pushed数组中的元素依次压入stack中；
  3. 先压入pushed中的元素，再进行判断，注意这里用while循环判断，如果stack的末尾元素与popped数组中的首元素相等，则将stack的末尾元素移除，index向后移动一位，循环往复，直到stack的末尾元素与index指向的元素不相等，再跳出循环，pushed数组中的元素再继续压入stack；
  4. 当stack为空，则返回true。

    11.3 代码

    1. class Solution {
    2.  public boolean validateStackSequences(int[] pushed, int[] popped) {
    3.      LinkedList<Integer> stack = new LinkedList<>();
    4.      int index = 0;
    5.      for (int push: pushed) {
    6.          stack.addLast(push);
    7.          while (!stack.isEmpty() && stack.peekLast() == popped[index]) {
    8.              stack.pollLast();
    9.              ++index;
    10.          }
    11.      }
    12.      return stack.isEmpty();
    13.  }
    14. }

    12、剑指 Offer 42.连续子数组的最大和

    这道题难点在于dp[i]该如何定义。

    12.1 题目

    输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。
    示例1:

    输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

12.2 思路

暴力破解法O(n2)就不说了，本题用动态规划，优化的版本时间复杂度为O(n)，空间复杂度为O(1)。

  1. 状态定义：令dp[i]表示以nums[i]结尾的连续子串的和的最大值；
  2. 转移方程：由于dp[i]中一定会包含nums[i]，当dp[i - 1] < 0时，由于dp[i - 1]为dp[i]的值做了负贡献，还不如仅有一个元素nums[i]，因此转移方程为：

image.png

  1. 初始状态：dp[0] = nums[0]；
  2. 返回值：返回dp数组的最大值，需要在遍历的过程中维护一个res，不断地求res和dp[i]的最大值，并赋值给res。

优化：根据上述思路可以得到12.3中未优化版本的代码，此时空间复杂度为O(n）；由于题目中给了一个数组nums，因此可将原数组nums作为dp数组，直接在nums上修改即可，优化后的代码为12.3优化版，空间复杂度为O(1)。

输入参数nums不计到空间复杂度。

12.3 代码

未优化版：

  1. class Solution {
  2.     public int maxSubArray(int[] nums) {
  3.         int len = nums.length;
  4.         int[] dp = new int[len];
  5.         dp[0] = nums[0];
  6.         int res = nums[0];
  7.         for (int i = 1; i < len; ++i) {
  8.             if (dp[i - 1] >= 0) {
  9.                 dp[i] = nums[i] + dp[i - 1];
  10.             } else {
  11.                 dp[i] = nums[i];
  12.             }
  13.             res = Math.max(res, dp[i]);
  14.         }
  15.         return res;
  16.     }
  17. }

优化版：

  1. class Solution {
  2.     public int maxSubArray(int[] nums) {
  3.         int len = nums.length;
  4.         int res = nums[0];
  5.         for (int i = 1; i < len; ++i) {
  6.             nums[i] += Math.max(nums[i - 1], 0);
  7.             res = Math.max(res, nums[i]);
  8.         }
  9.         return res;
  10.     }
  11. }

13、剑指 Offer 66.构建乘积数组

13.1 题目

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
示例:

输入: [1,2,3,4,5] 输出: [120,60,40,30,24]

13.2 思路

参考答案里用动态规划，本题不用动态规划也可以做，时间复杂度和空间复杂度均为O(n)。

  1. 正向遍历数组，获取数组numsAsc[]，numsAsc[i]表示数组a中前i个元素（不包含i）的乘积；
  2. 反向遍历数组，获取数组numsDesc[]，numsDesc[i]表示数组a中i之后的元素（不包含i）的乘积；
  3. 获取最终的结果数组res[]，res[i] = numsAsc[i] * numsDesc[i]。

    代码优化时，只需要一个res[]，第一步和第二步均在这个res[]上操作。优化后的代码不容易写正确。

13.3 代码

  1. class Solution {
  2.     public int[] constructArr(int[] a) {
  3.         int len = a.length;
  4.         int[] res = new int[len];
  5.         for (int i = 0, val = 1; i < len; val *= a[i], ++i) {
  6.             res[i] = val;
  7.         }
  8.         for (int i = len - 1, val = 1; i >= 0; val *= a[i], --i) {
  9.             res[i] *= val;
  10.         }
  11.         return res;
  12.     }
  13. }

14、剑指 Offer 40.最小的k个数

14.1 题目

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：

输入：arr = [3,2,1], k = 2 输出：[1,2] 或者 [2,1]

示例 2：

输入：arr = [0,1,2,1], k = 1 输出：[0]

14.2 思路

本题是快速排序的一种变种。题目只要求返回最小的 k 个数，对这 k 个数的顺序并没有要求。因此，只需要将数组划分为最小的k个数和其他数字两部分即可，而快速排序的哨兵（基准数）划分可完成此目标。根据快速排序原理，如果某次哨兵划分后基准数对应的下标与k相等 ，那么此时基准数左边的所有数字（不包含基准数）便是题目所求的最小的k个数 。

算法流程：

  1. getLeastNumbers() 函数：
    1. 若 k 大于数组长度，则直接返回整个数组；
    2. 否则执行并返回 quickSort() 即可；

  2. quickSort() 函数：

    注意，此时 quickSort() 的功能不是排序整个数组，而是搜索并返回最小的k个数。

    1. 哨兵划分：划分完毕后，基准数为 arr[left] ，左 / 右子数组区间分别为 [start, left - 1] , [left+ 1, end]；

    2. 递归或返回：

      1. 若 k < left，代表最终想要的哨兵位置在左子数组，则递归左子数组；
      2. 若 k > left ，代表最终想要的哨兵位置在右子数组，则递归右子数组；
      3. 若 k == left ，代表此时基准数所在的下标就是我们最终想要的哨兵位置，则直接返回数组前 left个数字即可；

        14.3 代码

        ```java class Solution { public int[] getLeastNumbers(int[] arr, int k) { if (arr == null) { return null; } if (arr.length <= k) { return arr; } return quickSort(arr, k, 0, arr.length - 1); }

      private int[] quickSort(int[] arr, int k, int start, int end) { int left = start, right = end; int pivot = arr[start]; while (left < right) {

      1.   while (left < right && arr[right] >= pivot) {
      2.       --right;
      3.   }
      4.   while (left < right && arr[left] <= pivot) {
      5.       ++left;
      6.   }
      7.   swap(arr, left, right);

      } swap(arr, left, start); if (left > k) {

      1.   return quickSort(arr, k, start, left - 1);

      } if (left < k) {

      1.   return quickSort(arr, k, left + 1, end);

      } return Arrays.copyOf(arr, k); }

      private void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } } ```

      15、剑指 Offer 53 - I.在排序数组中查找数字 I

      15.1 题目

      统计一个数字在排序数组中出现的次数。
      示例 1:

      输入: nums = [5,7,7,8,8,10], target = 8 输出: 2

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6 输出: 0

15.2 思路

排序数组查找数字，显然用二分查找，不同的是本题数组中存在重复元素，需要返回target在数组中出现的次数。

  1. 常规的二分查找写法，算出mid，然后移动left和right向中间搜索；
  2. 当nums[mid]== target时，说明我们找到了要找的元素，此时可以：
    1. 由mid向两边搜索，一旦搜索的元素不等于target时，向右或者向左搜索的指针就停止；
    2. 由当前left和right向mid逼近，一旦nums[left]==target或者nums[right]==target，就说明找到了target在nums数组中的边界，停止，最后通过left和right计算target数组的长度，返回个数。
  3. 注意while的终止条件，当数组元素为[1], target=1时，还需要走一次while循环，因此left要==right。

    15.3 代码

    1. class Solution {
    2.  public int search(int[] nums, int target) {
    3.      int left = 0, right = nums.length - 1;
    4.      // 当数组元素为[1], target=1时，还需要走一次while循环，因此left要==right
    5.      while (left <= right) {
    6.          int mid = (left + right) >> 1;
    7.          if (nums[mid] > target) {
    8.              right = mid - 1;
    9.          } else if (nums[mid] < target) {
    10.              left = mid + 1;
    11.          } else {
    12.              // 让left和right都逼近mid，直到与target相等停止，最后算长度就是个数
    13.              while (nums[left] != target) {
    14.                  ++left;
    15.              }
    16.              while (nums[right] != target) {
    17.                  --right;
    18.              }
    19.              return right - left + 1;
    20.          }
    21.      }
    22.      return 0;
    23.  }
    24. }

    16、剑指 Offer 11.旋转数组的最小数字

    背下来吧，这些边界条件和—right，是真想不到。

    16.1 题目

    把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。
    示例 1：

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

示例 2：

输入：numbers = [2,2,2,0,1] 输出：0

16.2 思路

参考：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/solution/mian-shi-ti-11-xuan-zhuan-shu-zu-de-zui-xiao-shu-3/

16.3 代码

  1. class Solution {
  2.     public int minArray(int[] numbers) {
  3.         int left = 0, right = numbers.length - 1, mid = 0;
  4.         while (left < right) {
  5.             mid = (left + right) >> 1;
  6.             if (numbers[mid] > numbers[right]) {
  7.                 left = mid + 1;
  8.             } else if (numbers[mid] < numbers[right]) {
  9.                 right = mid;
  10.             } else {
  11.                 --right;
  12.             }
  13.         }
  14.         return numbers[left];
  15.     }
  16. }

17、剑指 Offer 51.数组中的逆序对

小米三面就问的这道题目……

17.1 题目

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:

输入: [7,5,6,4] 输出: 5

17.2 思路

  1. 本体是归并排序的变种，大致流程可以参考归并排序的模板；

  2. 至于何时判断数组中的逆序对，合并阶段本质上是合并两个排序数组的过程，而每当遇到左子数组当前元素 > 右子数组当前元素时，意味着 「左子数组当前元素至末尾元素」 与 「右子数组当前元素」 构成了若干 「逆序对」。因此，考虑在归并排序的合并阶段统计「逆序对」数量，完成归并排序时，也随之完成所有逆序对的统计。

    17.3 代码

    1. class Solution {
    2.  private int cnt;
    4.  public int reversePairs(int[] nums) {
    5.      merge(nums, 0, nums.length - 1);
    6.      return this.cnt;
    7.  }
    9.  private void merge(int[] nums, int left, int right) {
    10.      int mid = left + ((right - left) >> 1);
    11.      // 当left == right时，数组里只有一个元素，不需要再划分了
    12.      if (left < right) {
    13.          // 划分左子数组
    14.          merge(nums, left, mid);
    15.          // 划分右子数组
    16.          merge(nums, mid + 1, right);
    17.          // 将左右子数组综合排序
    18.          mergeSort(nums, left, right, mid);
    19.      }
    20.  }
    22.  private void mergeSort(int[] nums, int left, int right, int mid) {
    23.      int[] tempArray = new int[right - left + 1];
    24.      int indexTempArray = 0, leftArrayIndex = left, rightArrayIndex = mid + 1;
    26.      while (leftArrayIndex <= mid && rightArrayIndex <= right) {
    27.          if (nums[leftArrayIndex] <= nums[rightArrayIndex]) {
    28.              tempArray[indexTempArray++] = nums[leftArrayIndex++];
    29.          } else {
    30.              // 计算逆序对
    31.              this.cnt += mid - leftArrayIndex + 1;
    32.              tempArray[indexTempArray++] = nums[rightArrayIndex++];
    33.          }
    34.      }
    36.      // 右子数组剩余部分放进tempArray
    37.      while (rightArrayIndex <= right) {
    38.          tempArray[indexTempArray++] = nums[rightArrayIndex++];
    39.      }
    41.      // 左子数组剩余部分放进tempArray
    42.      while (leftArrayIndex <= mid) {
    43.          tempArray[indexTempArray++] = nums[leftArrayIndex++];
    44.      }
    46.      // 将排好序的tempArray替换到原数组nums里对应的起始位置
    47.      for (int k = 0; k < tempArray.length; ++k) {
    48.          nums[left + k] = tempArray[k];
    49.      }
    50.  }
    51. }

    18、剑指 Offer 61.扑克牌中的顺子

    18.1 题目

    从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
    示例 1:

    输入: [1,2,3,4,5] 输出: True

示例 2:

输入: [0,0,1,2,5] 输出: True

18.2 思路

5张牌是顺子，则满足：

  1. 除大小王之外，所有牌无重复；
  2. 设5张牌中最大的牌为max，最小的牌为min（大小王除外），则需满足：max - min < 5（这一点很关键，确认了这一点后代码就好写了）。

为此有两种方法：
（1）集合set + 遍历

  1. 遍历5张牌，遇到大小王（0）直接跳过；
  2. 判断牌的值是否重复，利用set集合判断，重复直接返回false；
  3. 获取最大和最小的牌，维护max和min，遍历的时候不断更新这两个值；
  4. 判断max - min < 5是否成立。

复杂度分析：

  1. 时间复杂度 O(N) = O(5) = O(1) ： 其中 N 为 nums 长度，本题中 N = 5 ；遍历数组使用 O(N) 时间；
  2. 空间复杂度 O(N) = O(5) = O(1) ： 用于判重的辅助 Set 使用 O(N) 额外空间。

（2）排序 + 遍历

  1. 先对数组进行排序；
  2. 判断当前值是否是0，并用一个joker记录0对应的下标，最终joker值为最后一个0对应的后面一个元素的下标；
  3. 判断是否重复，遍历数组，用nums[i + 1] == nums[i]来判断，如果重复直接返回false；
  4. 最大的元素为排序后数组中最后一个元素，最小的非0元素为joker对应的元素，判断max - min < 5是否成立。

复杂度分析：

  1. 时间复杂度 O(N log N) = O(5 log 5) = O(1)： 其中 N 为 nums 长度，本题中 N = 5 ；数组排序使用 O(N log N)时间；
  2. 空间复杂度 O(1)： 变量 joker 使用 O(1)大小的额外空间。

    18.3 代码

    1. class Solution {
    2.  public boolean isStraight(int[] nums) {
    3.      Set<Integer> set = new HashSet<>();
    4.      int max = 0, min = 14;
    5.      for (int num: nums) {
    6.          if (num == 0) {
    7.              continue;
    8.          }
    9.          if (set.contains(num)) {
    10.              return false;
    11.          }
    12.          max = Math.max(num, max);
    13.          min = Math.min(num, min);
    14.          set.add(num);
    15.      }
    16.      return max - min < 5;
    17.  }
    18. }
    1. class Solution {
    2.  public boolean isStraight(int[] nums) {
    3.      Arrays.sort(nums);
    4.      int joker = 0;
    5.      for (int i = 0 ; i < 4; ++i) {
    6.          if (nums[i] == 0) {
    7.              ++joker;
    8.          }
    9.          else if (nums[i + 1] == nums[i]) {
    10.              return false;
    11.          }
    12.      }
    13.      return nums[nums.length - 1] - nums[joker] < 5;
    14.  }
    15. }

    19、剑指 Offer 12.矩阵中的路径

    好题。

    19.1 题目

    给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
    例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）：
    image.png
    示例 1：

    输入：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED” 输出：true

示例 2：

输入：board = [[“a”,”b”],[“c”,”d”]], word = “abcd” 输出：false

19.2 思路

这道题是深度优先搜索和回溯思想的结合。

  1. 由于不能走已经走过的格子，因此需要维护一个二维数组visited，来记录哪些坐标已经走过了，dfs到上下左右的坐标时，需要判断当前的坐标是否已经走过，走过就不能再走了直接return；
  2. 注意dfs的起点，题中意思是路径的起始点可以是矩阵中的任意点，因此需要遍历这个二维数组，以数组中的任意一个点作为路径的起始点去dfs；

  3. 在dfs里需要注意回溯思想中的“添加”和“回退”。进入dfs后，开始下一轮dfs前，如果当前坐标对应的值可以添加到路径，则需要将当前坐标对应的visited二维数组中的点置为true，当前点的dfs退出前，需要将当前坐标对应的visited二维数组中的点置为false；

    19.3 代码

    1. class Solution {
    2.  private boolean[][] visited;
    3.  public boolean exist(char[][] board, String word) {
    4.      int h = board.length;
    5.      int w = board[0].length;
    6.      visited = new boolean[h][w];
    7.      for (int i = 0; i < h; ++i) {
    8.          for (int j = 0; j < w; ++j) {
    9.              if (dfs(i, j, 0, board, word)) {
    10.                  return true;
    11.              }
    12.          }
    13.      }
    14.      return false;
    15.  }
    17.  private boolean dfs(int i, int j, int index, char[][] board, String word) {
    18.      if (board[i][j] != word.charAt(index)) {
    19.          return false;
    20.      }
    21.      if (index == word.length() - 1) {
    22.          return true;
    23.      }
    25.      visited[i][j] = true;
    26.      int[][] directions = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    27.      for (int[] direction: directions) {
    28.          int ii = i + direction[0];
    29.          int jj = j + direction[1];
    30.          if (isValid(ii, jj, board) && !visited[ii][jj]) {
    31.              if (dfs(ii, jj, index + 1, board, word)) {
    32.                  return true;
    33.              }
    34.          }
    35.      }
    36.      visited[i][j] = false;
    37.      return false;
    38.  }
    40.  private boolean isValid(int i, int j, char[][] board) {
    41.      int h = board.length;
    42.      int w = board[0].length;
    43.      return i >= 0 && i < h && j >= 0 && j < w;
    44.  }
    45. }

    20、剑指 Offer 53 - II.0～n-1中缺失的数字

    边界条件很容易出错…..

    20.1 题目

    一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
    示例 1:

    输入: [0,1,3] 输出: 2

示例 2:

输入: [0,1,2,3,4,5,6,7,9] 输出: 8

20.2 思路

排序数组中的搜索问题，首先想到二分法解决。
本题有两种思路：

  1. 数学法：0到数组中最后一个数字正常的前n项和 - 数组中所有元素之和，差就是缺失的数字。时间复杂度为O(n)；
  2. 二分查找，时间复杂度为O(lgn)。

二分查找虽然不好想，但时间复杂度优于数学法，因此面试时还是用二分查找。

  1. 根据题意，数组可以按照以下规则划分为两部分，其中i为数组下标：
    1. 左子数组： nums[i] =i ；
    2. 右子数组： nums[i] != i；
  2. 缺失的数字等于 “右子数组的首位元素” 对应的下标；因此考虑使用二分法查找 “右子数组的首位元素”。

image.png

while循环里的结束条件是left <= right，这个可以用以下两个例子带入来确定：[0,1,2,3,4,5,6,7,9]，[0,2,3,4,5]

20.3 代码

  1.  class Solution {
  2.     public int missingNumber(int[] nums) {
  3.         int left = 0, right = nums.length - 1;
  4.         // 跳出循环时，left 和 right 分别指向 “右子数组的首位元素” 和 “左子数组的末位元素” ，
  5.         // 因此返回 left 即可。
  6.         while (left <= right) {
  7.             int mid = (left + right) >> 1;
  8.             if (nums[mid] == mid) {
  9.                 left = mid + 1;
  10.             } else {
  11.                 right = mid - 1;
  12.             }
  13.         }
  14.         return left;
  15.     }
  16. }

21、剑指 Offer 29.顺时针打印矩阵

21.1 题目

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5]

示例 2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] 输出：[1,2,3,4,8,12,11,10,9,5,6,7]

21.2 思路

  1. 分4个方向，left -> right、top -> bottom、right -> left、bottom -> top；
  2. while循环结束条件可以套一个例子来确定，当=时还是可以再一轮的；

  3. 一定要注意每次for循环的判断条件中，需要加上index < h * w这个判断，即如果数组元素已经填满了，就该直接结束循环，这里每个for循环都这么判断了下，即使不满足也不会立刻跳出while循环，下一次while循环也不会进去了。

    21.3 代码

    1. class Solution {
    2.  public int[] spiralOrder(int[][] matrix) {
    3.      if (matrix.length == 0) {
    4.          return new int[]{};
    5.      }
    6.      int h = matrix.length;
    7.      int w = matrix[0].length;
    8.      int[] res = new int[h * w];
    9.      int top = 0, bottom = h - 1, left = 0, right = w - 1, index = 0;
    11.      while (top <= bottom && left <= right) {
    12.          // left -> right
    13.          for (int i = left; index < h * w && i <= right; ++i) {
    14.              res[index++] = matrix[top][i];
    15.          }
    16.          ++top;
    18.          // top -> bottom
    19.          for (int i = top; index < h * w && i <= bottom; ++i) {
    20.              res[index++] = matrix[i][right];
    21.          }
    22.          --right;
    24.          // right -> left
    25.          for (int i = right; index < h * w && i >= left; --i) {
    26.              res[index++] = matrix[bottom][i];
    27.          }
    28.          --bottom;
    30.          // bottom -> top
    31.          for (int i = bottom; index < h * w && i >= top; --i) {
    32.              res[index++] = matrix[i][left];
    33.          }
    34.          ++left;
    35.      }
    36.      return res;
    37.  }
    38. }

    22、剑指 Offer 04.二维数组中的查找

    22.1 题目

    在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
    示例:
    现有矩阵 matrix 如下：

    [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]

给定 target = 5，返回 true。
给定 target = 20，返回 false。

22.2 思路

可以从矩阵的左下角和右上角开始搜索，由于矩阵是每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序，因此在搜索时，以左下角为例：

  1. 当target大于当前矩阵点时，当前点向右移动一格搜索；
  2. 当target小于当前矩阵点时，当前点向上移动一格搜索；
  3. 当target等于当前矩阵的时，直接返回true；
  4. 如果超出了矩阵范围还没有返回true，则返回false，说明target不在矩阵中。

    22.3 代码

    1. class Solution {
    2.  public boolean findNumberIn2DArray(int[][] matrix, int target) {
    3.      if (matrix.length == 0) {
    4.          return false;
    5.      }
    6.      int h = matrix.length;
    7.      int w = matrix[0].length;
    8.      int i = h - 1, j = 0;
    9.      while (i < h && i >= 0 && j < w && j >= 0) {
    10.          if (target > matrix[i][j]) {
    11.              ++j;
    12.          } else if (target < matrix[i][j]) {
    13.              --i;
    14.          } else {
    15.              return true;
    16.          }
    17.      }
    18.      return false;
    19.  }
    20. }

    23、剑指 Offer 57 - II. 和为s的连续正数序列

    23.1 题目

    输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
    示例 1：

    输入：target = 9 输出：[[2,3,4],[4,5]]

示例 2：

输入：target = 15 输出：[[1,2,3,4,5],[4,5,6],[7,8]]

23.2 思路

  1. 本题是双指针的题目，用左右两个指针来表示连续正整数的范围，需要计算左右两个指针之间的连续正整数之和sum，并与target比较，需要注意左右两个指针只会向右单向遍历；
  2. 左右两个指针的初始化位置：left = 1， right = 2，需要注意左右两个指针不能重合（题目规定至少两个连续正整数）；
  3. 当sum < target时，因为左右两个指针都只向右移动，因此将右指针向右移1位，使sum变大一些；
  4. 当sum > target时，说明以left为起点的连续正整数不存在一个left，使sum == target，因为左右两个指针都只向右移动，因此将左指针向右移动1位，使区间内正整数的数量减1，使sum变小一些；
  5. 当sum == target时，记录此时区间内的数组成的数组并放入res结果中，因为以left为起点的合法解只有一个，需要枚举下一个起点，因此将左指针向右移动1位；

  6. 退出条件是left > right，因为至少包含一个正整数，因此left != right。

    23.3 代码

    1. class Solution {
    2.  public int[][] findContinuousSequence(int target) {
    3.      List<int[]> res = new ArrayList<>();
    4.      int left = 1, right = 2;
    5.      while (left < right) {
    6.          if (getSum(left, right) < target) {
    7.              ++right;
    8.          } else if (getSum(left, right) > target) {
    9.              ++left;
    10.          } else {
    11.              int[] array = new int[right - left + 1];
    12.              for (int i = left; i <= right; ++i) {
    13.                  array[i - left] = i;
    14.              }
    15.              res.add(array);
    16.              ++left;
    17.          }
    18.      }
    19.      return res.toArray(new int[res.size()][]);
    20.  }
    22.  private int getSum(int left, int right) {
    23.      return ((left + right) * (right - left + 1)) >> 1;
    24.  }
    25. }

    24、找到所有数组中消失的数字

    真顶。

    24.1 题目

    给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
    示例 1：

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

示例 2：

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

24.2 思路

本题有两个思路：

  1. 借助一个额外的set判断是否存在，不推荐，空间复杂度为O(n)；
  2. 数组原地处理，具体算法为：
    1. 遍历数组，尽量将数组元素nums[i]放到数组中下标为nums[i] - 1的位置，“放”这个操作可以用交换的方式进行；
    2. 因为数组中允许出现重复的数字，在交换时，当数组中下标为nums[i] - 1的位置已经放置了nums[i]，则当前数组元素不再处理，继续往后走一格；
    3. 处理完一遍数组后，再重新遍历一次数组，将数组中nums[i] != i + 1，将i + 1放置结果集，最后返回结果集。

      24.3 代码

      引入set：
      1. class Solution {
      2. public List<Integer> findDisappearedNumbers(int[] nums) {
      3.   List<Integer> res = new ArrayList<>();
      4.   int n = nums.length;
      5.   Set<Integer> set = new HashSet<>();
      6.   for (int num: nums) {
      7.       set.add(num);
      8.   }
      9.   for (int i = 1; i <= n; ++i) {
      10.       if (!set.contains(i)) {
      11.           res.add(i);
      12.       }
      13.   }
      14.   return res;
      15. }
      16. }
      不引入额外的空间：
      1. class Solution {
      2. public List<Integer> findDisappearedNumbers(int[] nums) {
      3.   int len = nums.length;
      4.   int index = 0;
      5.   while (index < len) {
      6.       if (nums[index] == index + 1) {
      7.           ++index;
      8.       } else {
      9.           int targetIndex = nums[index] - 1;
      10.           if (nums[targetIndex] == nums[index]) {
      11.               ++index;
      12.           } else {
      13.               int tmp = nums[targetIndex];
      14.               nums[targetIndex] = nums[index];
      15.               nums[index] = tmp;
      16.           }
      17.       }
      18.   }
      19.   List<Integer> res = new ArrayList<>();
      20.   for (int i = 0; i < len; ++i) {
      21.       if (nums[i] != i + 1) {
      22.           res.add(i + 1);
      23.       }
      24.   }
      25.   return res;
      26. }
      27. }

      25、287. 寻找重复数

      这尼玛谁想的出来啊…

      25.1 题目

      给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。
      示例 1：

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

示例 2：

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

25.2 思路

本题可以转换成数组的环形链表。
image.png
链表对应的数组中的移动：

  1. 移动一次：slow = nums[slow]
  2. 移动两次：fast = nums[nums[fast]]

    25.3 代码

    1. class Solution {
    2.  public int findDuplicate(int[] nums) {
    3.      int fast = 0, slow = 0;
    4.      slow = nums[slow];
    5.      fast = nums[nums[fast]];
    6.      while (slow != fast) {
    7.          fast = nums[nums[fast]];
    8.          slow = nums[slow];
    9.      }
    10.      fast = 0;
    11.      while (fast != slow) {
    12.          fast = nums[fast];
    13.          slow = nums[slow];
    14.      }
    15.      return slow;
    16.  }
    17. }

    26、283. 移动零

    26.1 题目

    给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。
    示例 1:

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

示例 2:

输入: nums = [0] 输出: [0]

26.2 思路

本题有两种思路：

  1. 暴力法：遍历数组时，检查当前元素和前一个元素，如果当前元素是0，则不做处理往后移动1位；否则向前依次遍历检查，将当前元素和前一个是0的元素交换，直到前一个元素不是0才停止交换，随后继续向后遍历；

  2. 双指针：

    1. 左指针之前的元素（不包含左指针）是排好的，不用动的；

    2. 右指针向后依次检查，如果是0则继续往后遍历；如果不是0，则与左指针交换，然后左指针和右指针依次向后移动一位。

      26.3 代码

      暴力法：

      1. class Solution {
      2. public void moveZeroes(int[] nums) {
      3.   int len = nums.length, index = 1;
      4.   while (index < len) {
      5.       int nextIndex = index + 1;
      6.       while (index > 0 && nums[index - 1] == 0) {
      7.           swap(nums, index - 1, index);
      8.           --index;
      9.       }
      10.       index = nextIndex;
      11.   }
      12. }
      14. private void swap(int[] nums, int i, int j) {
      15.   int tmp = nums[i];
      16.   nums[i] = nums[j];
      17.   nums[j] = tmp;
      18. }
      19. }

      双指针：

      1. class Solution {
      2. public void moveZeroes(int[] nums) {
      3.   int left = 0, right = 0;
      4.   while (right < nums.length) {
      5.       if (nums[right] != 0) {
      6.           swap(nums, left, right);
      7.           ++left;
      8.       }
      9.       ++right;
      10.   }
      11. }
      13. private void swap(int[] nums, int left, int right) {
      14.   int tmp = nums[left];
      15.   nums[left] = nums[right];
      16.   nums[right] = tmp;
      17. }
      18. }

      27、215. 数组中的第K个最大元素

      27.1 题目

      给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
      示例 1:

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

示例 2:

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

27.2 思路

本题题目清晰，看上去第一个思路就是对数组排序，然后取倒数第k个元素返回，但是面试时肯定不能直接调Arrays.sort，且本题可以在排序的时候就能确认值，而无需等到数组全部排好序后再返回。本题可以基于快排的思路上解决。

  1. 整体思路还是快排的思路，也不完全是快排；
  2. 当在quickHelper函数里调用partition方法获取到了已经在数组中确定了位置的pivot下标时，可以与nums.length - k比较：
    1. 如果相等，直接返回nums[pivot]，pivot左右两边的数组是否排好序已经不用关心了；
    2. 如果pivot > nums.length - k，则目标下标肯定在pivot左侧，因此只需递归左子数组即可；
    3. 如果pivot < nums.length - k，则目标下标肯定在pivot右侧，因此只需递归右子数组即可；
    4. 在quickHelper函数里，无需关系start >= end的场景，因为只需关系pivot和目标下标的关系，无需关心数组排序。

  3. 相比基本的快排，本题在以下两个方面做了优化：

    1. 当pivot就是目标下标时，直接返回，无需再对左右两个子数组排序了；

    2. 当pivot不是目标下标时，仅需递归一个子数组，而无需遍历左右两个子数组。

      27.3 代码

      1. class Solution {
      2. private int target;
      4. public int findKthLargest(int[] nums, int k) {
      5.   this.target = nums.length - k;
      6.   return quickHelper(nums, 0, nums.length - 1);
      7. }
      9. private int quickHelper(int[] nums, int start, int end) {
      10.   int pivot = partition(nums, start, end);
      11.   if (pivot < target) {
      12.       return quickHelper(nums, pivot + 1, end);
      13.   } else if (pivot > target) {
      14.       return quickHelper(nums, start, pivot - 1);
      15.   } else {
      16.       return nums[pivot];
      17.   }
      18. }
      20. private int partition(int[] nums, int start, int end) {
      21.   int left = start, right = end, pivot = nums[start];
      22.   while (left < right) {
      23.       while (left < right && nums[right] >= pivot) {
      24.           --right;
      25.       }
      26.       while (left < right && nums[left] <= pivot) {
      27.           ++left;
      28.       }
      29.       swap(nums, left, right);
      30.   }
      31.   swap(nums, start, left);
      32.   return left;
      33. }
      35. private void swap(int[] nums, int left, int right) {
      36.   int tmp = nums[left];
      37.   nums[left] = nums[right];
      38.   nums[right] = tmp;
      39. }
      40. }

      28、347. 前 K 个高频元素

      28.1 题目

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

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

示例 2:

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

28.2 思路

  1. 用map存每一个数字出现的次数，key为数组，value为数字出现的次数；
  2. 对map按value降序排序（用stream的一套处理流程要记住）；
  3. 取排序后的map的前k个元素，返回对应的key。

这种思路不是最优解法，但堆想不到。

28.3 代码

  1. class Solution {
  2.     public int[] topKFrequent(int[] nums, int k) {
  3.         Map<Integer, Integer> map = new HashMap<>();
  4.         for (int num : nums) {
  5.             if (map.containsKey(num)) {
  6.                 map.put(num, map.get(num) + 1);
  7.             } else {
  8.                 map.put(num, 1);
  9.             }
  10.         }
  12.         List<Map.Entry<Integer, Integer>> list =
  13.                 map.entrySet().stream().sorted(Map.Entry.<Integer, Integer>comparingByValue().reversed()).collect(Collectors.toList());
  14.         int[] res = new int[k];
  15.         for (int i = 0; i < k; ++i) {
  16.             res[i] = list.get(i).getKey();
  17.         }
  18.         return res;
  19.     }
  20. }

29、75. 颜色分类

荷兰国旗问题，我是想不出来这个题解，而且条件判断很容易出错。三路快排，顶不住顶不住……

29.1 题目

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻并按照红色、白色、蓝色顺序排列。我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。必须在不使用库的sort函数的情况下解决这个问题。
示例 1：

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

示例 2：

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

29.2 思路

image.png
看题解吧：https://leetcode-cn.com/problems/sort-colors/solution/yan-se-fen-lei-by-leetcode-solution/

29.3 代码

  1. class Solution {
  2.     public void sortColors(int[] nums) {
  3.         int p0 = 0, index = 0, p2 = nums.length - 1;
  4.         while (index <= p2) {
  5.             if (nums[index] == 0) {
  6.                 swap(nums, p0, index);
  7.                 ++index;
  8.                 ++p0;
  9.             } else if (nums[index] == 1) {
  10.                 ++index;
  11.             } else {
  12.                 // nums[index] == 2
  13.                 swap(nums, index, p2);
  14.                 --p2;
  15.             }
  16.         }
  17.     }
  19.     private void swap(int[] nums, int left, int right) {
  20.         int tmp = nums[left];
  21.         nums[left] = nums[right];
  22.         nums[right] = tmp;
  23.     }
  24. }

30、最大子数组和

30.1 题目

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。
示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1] 输出：1

示例 3：

输入：nums = [5,4,-1,7,8] 输出：23

30.2 思路

动态规划的经典题目，暴力破解两次for循环就不说了。

  1. 令dp[i]表示以下标为i结尾的最大子数组和，则有转移方程：dp[i + 1] = Math.max(dp[i] + nums[i + 1], nums[i + 1])，dp[i]强调一定要以i这个下标结尾；
  2. 题目要求的最终解并不一定是以数组最后一个元素结尾的连续数组，以数组中任意一个元素结尾的连续数组均可以，只是要返回一个最大值，因此在遍历dp数组时需要维护一个最大值；
  3. 最终返回的是这个最大值，而不是dp[len - 1]；
  4. 由于dp数组中，dp[i + 1]仅与dp[i]有关系，因此可以考虑用一个变量代替这个一维数组dp，降低空间复杂度。

    30.3 代码

    一维dp数组：
    1. class Solution {
    2.  public int maxSubArray(int[] nums) {
    3.      int len = nums.length;
    4.      int[] dp = new int[len];
    5.      dp[0] = nums[0];
    6.      int res = nums[0];
    7.      for (int i = 1; i < len; ++i) {
    8.          dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
    9.          res = Math.max(res, dp[i]);
    10.      }
    11.      return res;
    12.  }
    13. }
    优化后的dp：
    1. class Solution {
    2.  public int maxSubArray(int[] nums) {
    3.      int len = nums.length;
    4.      int dp = nums[0];
    5.      int res = nums[0];
    6.      for (int i = 1; i < len; ++i) {
    7.          dp = Math.max(nums[i], dp + nums[i]);
    8.          res = Math.max(res, dp);
    9.      }
    10.      return res;
    11.  }
    12. }

    31、128. 最长连续序列

    这思路我想不出来……

    31.1 题目

    给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
    请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
    示例 1：

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

示例 2：

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

31.2 思路

本体不是动态规划的思想，因为没有排序，也不好用双指针，实际就是一个遍历优化的思想。

  1. 先将nums数组中的元素放入一个set集合，这个set集合在后面判断的时候会用到，相当于用这个set集合的空间换时间，来满足时间复杂度 O(n) 的要求；
  2. 如果已知有一个 x, x+1, x+2,…, x+y 的连续序列，而我们却重新从 x+1，x+2 或者是 x+y 处开始尝试匹配，那么得到的结果肯定不会优于枚举 x 为起点的答案，因此遍历set集合，如果当前元素-1的值也在set里，就直接跳过，即最终目的是想从连续序列的最开始（最小值）开始遍历；
  3. 内层循环是只有当前元素前面没有元素在set里，才当元素进入内层循环，此时就while循环看当前元素 + 1的值是否在set里，如果在则继续循环，如果不在则退出，维护最大结果值，此次内层循环结束。

    31.3 代码

    1. class Solution {
    2.  public int longestConsecutive(int[] nums) {
    3.      Set<Integer> set = new HashSet<>();
    4.      for (int num: nums) {
    5.          set.add(num);
    6.      }
    7.      int res = 0;
    8.      for (int num: nums) {
    9.          if (!set.contains(num - 1)) {
    10.              int currentNum = num;
    11.              int cnt = 1;
    12.              while (set.contains(currentNum + 1)) {
    13.                  currentNum += 1;
    14.                  cnt += 1;
    15.              }
    16.              res = Math.max(res, cnt);
    17.          }
    18.      }
    19.      return res;
    20.  }
    21. }

    32、300. 最长递增子序列

    32.1 题目

    给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
    示例 1：

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

示例 2：

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

示例 3：

输入：nums = [7,7,7,7,7,7,7] 输出：1

32.2 思路

  1. 状态定义：令dp[i]表示以数组中下标为i结尾的最长上升子序列的长度，注意dp[i]一定要包含nums[i]；
  2. 转移方程：dp[i] = max(dp[j]) + 1，其中0 <= j < i且nums[i] > nums[j]；
  3. 初始状态：dp[0] = 1；
  4. 返回值：遍历dp数组时维护一个dp[i]的最大值，返回这个最大值。

    32.3 代码

    1. class Solution {
    2.  public int lengthOfLIS(int[] nums) {
    3.      if (nums == null || nums.length == 0) {
    4.          return 0;
    5.      }
    6.      int n = nums.length;
    7.      int res = 1;
    8.      int[] dp = new int[n];
    9.      dp[0] = 1;
    10.      for (int i = 1; i < n; ++i) {
    11.          int maxJ = 1;
    12.          for (int j = 0; j < i; ++j) {
    13.              if (nums[i] > nums[j]) {
    14.                  maxJ = Math.max(maxJ, dp[j]);
    15.                  dp[i] = maxJ + 1;
    16.                  res = Math.max(dp[i], res);
    17.              }
    18.          }
    19.      }
    20.      return res;
    21.  }
    22. }

    33、1. 两数之和

    33.1 题目

    给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。
    示例 1：

    输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

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

示例 3：

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

33.2 思路

本题有两种思路：暴力法和引入一个map降低时间复杂度的方法。

  1. 暴力法：双重for循环，时间复杂度O(n2)，空间复杂度O(1)；
  2. 引入map：为了降低时间复杂度，只能用空间换时间：
    1. 引入一个map，key存放nums中的元素，value存放元素对应的下标；
    2. 遍历nums数组，判断 target - nums[i] 是否在map里存在，如果存在，直接返回两个下标，如果不存在，则向map中插入k-v。

      33.3 代码

      暴力法：
      1. class Solution {
      2. public int[] twoSum(int[] nums, int target) {
      3.   if (nums == null || nums.length == 0) {
      4.       return new int[0];
      5.   }
      6.   for (int i = 0; i < nums.length; ++i) {
      7.       for (int j = i + 1; j < nums.length; ++j) {
      8.           if (nums[i] + nums[j] == target) {
      9.               return new int[]{i, j};
      10.           }
      11.       }
      12.   }
      13.   return null;
      14. }
      15. }
      引入map
      1. class Solution {
      2. public int[] twoSum(int[] nums, int target) {
      3.   if (nums == null || nums.length == 0) {
      4.       return new int[0];
      5.   }
      6.   Map<Integer, Integer> map = new HashMap<>();
      7.   for (int i = 0; i < nums.length; ++i) {
      8.       if (!map.containsKey(target - nums[i])) {
      9.           map.put(nums[i], i);
      10.       } else {
      11.           return new int[]{map.get(target - nums[i]), i};
      12.       }
      13.   }
      14.   return new int[0];
      15. }
      16. }

      34、56. 合并区间

      34.1 题目

      以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
      示例 1：

      输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

34.2 思路

  1. 当intervals数组为空，或者仅有一个元素，返回intervals数组；
  2. 对intervals数组，按照元素数组中的第一个值升序排序；
  3. 维护一个LinkedList的数据结构，遍历排序后的数组，将数组中的当前元素与list的尾元素比较，看是否需要合并区间，注意合并后的区间，左区间是Math.min(pre[0], cur[0])，右区间是Math.max(pre[1], cur[1])。

    34.3 代码

    1. class Solution {
    2.  public int[][] merge(int[][] intervals) {
    3.      if (intervals == null || intervals.length == 0 || intervals.length == 1) {
    4.          return intervals;
    5.      }
    6.      LinkedList<int[]> res = new LinkedList<>();
    7.      Arrays.sort(intervals, Comparator.comparingInt(interval -> interval[0]));
    8.      res.addLast(intervals[0]);
    9.      for (int i = 1; i < intervals.length; ++i) {
    10.          int[] pre = res.peekLast();
    11.          int[] cur = intervals[i];
    12.          if (pre[1] >= cur[0]) {
    13.              res.removeLast();
    14.              int left = Math.min(pre[0], cur[0]);
    15.              int right = Math.max(pre[1], cur[1]);
    16.              res.addLast(new int[]{left, right});
    17.          } else {
    18.              res.addLast(cur);
    19.          }
    20.      }
    21.      return res.toArray(new int[res.size()][2]);
    22.  }
    23. }

    35、494. 目标和

    35.1 题目

    给你一个整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个 表达式 ：例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-‘ ，然后串联起来得到表达式 “+2-1” 。返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
    示例 1：

    输入：nums = [1,1,1,1,1], target = 3 输出：5 解释：一共有 5 种方法让最终目标和为 3 。 -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3

示例 2：

输入：nums = [1], target = 1 输出：1

35.2 思路

本题是一道回溯的题目。但是写法与传统的回溯有略微不一样，代码中不用回退（因为多加了一个sum变量的原因）。

35.3 代码

  1. class Solution {
  2.     private int cnt;
  3.     public int findTargetSumWays(int[] nums, int target) {
  4.         trace(nums, target, 0, 0);
  5.         return cnt;
  6.     }
  8.     private void trace(int[] nums, int target, int index, int sum) {
  9.         if (index == nums.length) {
  10.             if (sum == target) {
  11.                 ++cnt;
  12.             }
  13.         } else {
  14.             trace(nums, target, index + 1, sum + nums[index]);
  15.             trace(nums, target, index + 1, sum - nums[index]);
  16.         }
  17.     }
  18. }

36、560. 和为 K 的子数组

前缀和 + map的思路太难理解了……

36.1 题目

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

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

示例 2：

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

36.2 思路

本题有三种做法：

  1. 枚举法（时间复杂度O(n2)）：
    1. 固定一个指针，统计这个指针之前的元素和，如果与k相等，则结果+1；
    2. 将这个指针遍历数组，遍历完毕后即统计了所有可能的情况。
  2. 前缀和（时间复杂度O(n2)）:
    1. 用一个数组preSum记录原数组nums中下标的前缀和，由于考虑后面逻辑里，数组中某个元素值为k，也算一个子数组，令preSum[i + 1]表示nums数组中[0, i]区间的元素和，preSum[0] = 0；
    2. 遍历数组，求出这个前缀和数组preSum的元素值；
    3. 将题目的求和为k的子数组的个数问题转换为：统计前缀和数组中，preSum[i] - preSum[j] == k的个数，需要两个指针双重for循环遍历所有场景，因此这里时间复杂度还是O(n2)。
  3. 前缀和 + 哈希表（时间复杂度O(n)）：
    1. 跟方法二思路类似，将问题转换为：统计前缀和数组中，前缀和为pre[i] - k = pre[j]的个数，其中0 <= j < i；

    2. 37.3 代码

      枚举法：
      1. class Solution {
      2. public int subarraySum(int[] nums, int k) {
      3.   if (nums == null || nums.length == 0) {
      4.       return 0;
      5.   }
      6.   int res = 0;
      7.   for (int i = 0; i < nums.length; ++i) {
      8.       int sum = 0;
      9.       for (int j = i; j >= 0; --j) {
      10.           sum += nums[j];
      11.           if (sum == k) {
      12.               ++res;
      13.           }
      14.       }
      15.   }
      16.   return res;
      17. }
      18. }
      前缀和数组
      1. class Solution {
      2. public int subarraySum(int[] nums, int k) {
      3.   int len = nums.length;
      4.   // preSum[i + 1]表示nums数组中[0, i]区间的元素和
      5.   int[] preSum = new int[len + 1];
      6.   preSum[0] = 0;
      7.   // 前缀和数组赋值
      8.   for (int i = 1; i <= len; ++i) {
      9.       preSum[i] = preSum[i - 1] + nums[i - 1];
      10.   }
      11.   // 统计前缀和数组中，preSum[i] - preSum[j] == k的个数
      12.   int cnt = 0;
      13.   for (int j = 0; j <= len; ++j) {
      14.       for (int i = j + 1; i <= len; ++i) {
      15.           if (preSum[i] - preSum[j] == k) {
      16.               ++cnt;
      17.           }
      18.       }
      19.   }
      20.   return cnt;
      21. }
      22. }
      前缀和 + 哈希表
      1. class Solution {
      2. public int subarraySum(int[] nums, int k) {
      3.   Map<Integer, Integer> map = new HashMap<>();
      4.   map.put(0, 1);
      5.   int pre = 0, res = 0;
      6.   for (int i = 0; i < nums.length; ++i) {
      7.       pre += nums[i];
      8.       if (map.containsKey(pre - k)) {
      9.           res += map.get(pre - k);
      10.       }
      11.       map.put(pre, map.getOrDefault(pre, 0) + 1);
      12.   }
      13.   return res;
      14. }
      15. }

      37、33. 搜索旋转排序数组

      37.1 题目

      整数数组 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 。
      示例 1：

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

示例 2：

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

示例 3：

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

37.2 思路

还是看这道题吧：剑指 Offer 11.旋转数组的最小数字

37.3 代码

  1. class Solution {
  2.     public int search(int[] nums, int target) {
  3.         for (int i = 0; i < nums.length; ++i) {
  4.             if (nums[i] == target) {
  5.                 return i;
  6.             }
  7.         }
  8.         return -1;
  9.     }
  10. }

38、55. 跳跃游戏

38.1 题目

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。
示例 1：

输入：nums = [2,3,1,1,4] 输出：true 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4] 输出：false 解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

38.2 思路

本题有两种思路：

  1. 动态规划（时间复杂度O(n2)，空间复杂度O(n)）：
    1. 状态定义：dp[i]表示是否能跳跃到数组下标为i的位置；
    2. 转移方程：对于dp[i]，枚举[0, i - 1]中的每个dp[j] = true的位置，j的取值范围是[0, i - 1]，如果存在nums[j] >= i - j，即代表dp[i]可以由[0, i - 1]中的一个位置跳跃过来，则dp[i] = true；
    3. 初始状态：dp[0] = true，数组首元素肯定可以跳跃到；
    4. 返回值：dp[nums.length() - 1]。
  2. 贪心算法（时间复杂度O(n)，空间复杂度O(1)）：

对于每一个可以到达的位置 x，它使得 x+1, x+2,…,x+nums[x] 这些连续的位置都可以到达。这样以来，我们依次遍历数组中的每一个位置，并实时维护最远可以到达的位置。对于当前遍历到的位置 x，如果它在最远可以到达的位置的范围内，那么我们就可以从起点通过若干次跳跃到达该位置，因此我们可以用 x +nums[x] 更新最远可以到达的位置。在遍历的过程中，如果最远可以到达的位置大于等于数组中的最后一个位置，那就说明最后一个位置可达，我们就可以直接返回 True 作为答案。反之，如果在遍历结束后，最后一个位置仍然不可达，我们就返回 False 作为答案。

38.3 代码

动态规划：

  1. class Solution {
  2.     public boolean canJump(int[] nums) {
  3.         int len = nums.length;
  4.         boolean[] dp = new boolean[len];
  5.         dp[0] = true;
  7.         for (int i = 1; i < len; ++i) {
  8.             for (int j = 0; j < i; ++j) {
  9.                 if (dp[j] && nums[j] >= i - j) {
  10.                     dp[i] = true;
  11.                     break;
  12.                 }
  13.             }
  14.         }
  15.         return dp[len - 1];
  16.     }
  17. }

贪心算法：

  1. class Solution {
  2.     public boolean canJump(int[] nums) {
  3.         int rightMax = 0;
  4.         for (int i = 0; i < nums.length; ++i) {
  5.             if (i <= rightMax) {
  6.                 rightMax = Math.max(rightMax, i + nums[i]);
  7.                 if (rightMax >= nums.length - 1) {
  8.                     return true;
  9.                 }
  10.             }
  11.         }
  12.         return false;
  13.     }
  14. }

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

39.1 题目

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：

  • 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1]

示例 3：

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

39.2 思路

排序数组，时间复杂度要求为 O(log n) ，基本思路就是二分法了。

  1. 通过二分法找到数组中值为target的下标mid；
  2. 将left和right指针均指向mid，即从mid向两边搜索，直到nums[left]或者nums[right]不等于target，这个过程中还需保证left和right在nums数组的下标范围内，返回left + 1, right - 1；
  3. 如果没有在while循环中返回，说明没有符合目标值的target，则返回[-1, -1]。

    39.3 代码

    1. class Solution {
    2.  public int[] searchRange(int[] nums, int target) {
    3.      if (nums == null || nums.length == 0) {
    4.          return new int[]{-1, -1};
    5.      }
    6.      int left = 0, right = nums.length - 1;
    7.      while (left <= right) {
    8.          int mid = (left + right) >> 1;
    9.          if (nums[mid] > target) {
    10.              --right;
    11.          } else if (nums[mid] < target) {
    12.              ++left;
    13.          } else {
    14.              // 复用之前的引用
    15.              left = mid;
    16.              right = mid;
    17.              while (left >= 0 && nums[left] == target) {
    18.                  --left;
    19.              }
    20.              while (right < nums.length && nums[right] == target) {
    21.                  ++right;
    22.              }
    23.              return new int[]{left + 1, right - 1};
    24.          }
    25.      }
    26.      return new int[]{-1, -1};
    27.  }
    28. }

    40、152. 乘积最大子数组

    这道动态规划，dp[i + 1]不是由的dp[i]直接推导出来的。

    40.1 题目

    给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。测试用例的答案是一个 32-位 整数。子数组 是数组的连续子序列。
    示例 1:

    输入: nums = [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: nums = [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

40.2 思路

本题有两个思路：

  1. 暴力法（时间复杂度为O(n2)，空间复杂度为O(1))：即用两个指针，第二个指针从第一个指针后一个位置向后搜索，搜索过程中维护乘积最大值；
  2. 动态规划（时间复杂度为O(n)，空间复杂度为O(n))：

image.png

  1. 动态规划优化空间（时间复杂度为O(n)，空间复杂度为O(1))：

    1. 由于2中的动态规划，maxArray[i + 1]仅跟maxArray[i]有关，minArray[i + 1]仅跟minArray[i]有关，因此可以用两个变量max和min分别代替maxArray和minArray数组，这就是所谓的滚动数组；

    2. 在for循环中重新计算max和min时，由于第一个是先更新了max，而第二个min的计算是用的更新前的max，因此需要两个变量maxPre和minPre存储更新前的max和min，max和min的计算都采用maxPre和minPre计算，这里容易出错。

      40.3 代码

      暴力法：

      1. class Solution {
      2. public int maxProduct(int[] nums) {
      3.   int res = Integer.MIN_VALUE;
      4.   for (int i = 0; i < nums.length; ++i) {
      5.       int val = nums[i];
      6.       res = Math.max(res, val);
      7.       for (int j = i + 1; j < nums.length; ++j) {
      8.           val *= nums[j];
      9.           res = Math.max(res, val);
      10.       }
      11.   }
      12.   return res;
      13. }
      14. }

      动态规划：

      1. class Solution {
      2. public int maxProduct(int[] nums) {
      3.   int len = nums.length;
      4.   int[] maxArray = new int[len];
      5.   int[] minArray = new int[len];
      6.   maxArray[0] = nums[0];
      7.   minArray[0] = nums[0];
      9.   for (int i = 1; i < len; ++i) {
      10.       maxArray[i] = Math.max(maxArray[i - 1] * nums[i], Math.max(minArray[i - 1] * nums[i], nums[i]));
      11.       minArray[i] = Math.min(maxArray[i - 1] * nums[i], Math.min(minArray[i - 1] * nums[i], nums[i]));
      12.   }
      13.   int res = nums[0];
      14.   for (int i = 1; i < len; ++i) {
      15.       res = Math.max(res, maxArray[i]);
      16.   }
      17.   return res;
      18. }
      19. }

      动态规划优化空间：

      1. class Solution {
      2. public int maxProduct(int[] nums) {
      3.   int len = nums.length;
      4.   int max = nums[0], min = nums[0], res = nums[0];
      6.   for (int i = 1; i < len; ++i) {
      7.       int maxPre = max, minPre = min;
      8.       max = Math.max(maxPre * nums[i], Math.max(minPre * nums[i], nums[i]));
      9.       min = Math.min(maxPre * nums[i], Math.min(minPre * nums[i], nums[i]));
      10.       res = Math.max(res, max);
      11.   }
      12.   return res;
      13. }
      14. }

      41、581. 最短无序连续子数组

      第一种思路可以接受，第二种思路太不好想了……

      41.1 题目

      给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。请你找出符合题意的最短子数组，并输出它的长度。
      示例 1：

      输入：nums = [2,6,4,8,10,9,15] 输出：5

解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
示例 2：

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

示例 3：

输入：nums = [1] 输出：0

41.2 思路

本题有两种思路：

  1. 排序数组（时间复杂度O(nlgn)，空间复杂度O(n))：
    1. 取原数组的一份拷贝，对拷贝进行排序；
    2. 将原数组和排序后的拷贝数组进行比较，左右两侧第一个不一样的数字即为边界。

注意找左右边界left和right时判断条件的处理。

  1. 双指针（时间复杂度O(n)，空间复杂度O(1))：

    1. 将数组分成三段，分别为左边升序排序好的、中间需要调整排序的、右边升序排序好的；且满足左边子数组中的元素都小于中间子数组，右边子数组中的元素都大于中间子数组；
    2. 起始时通过双指针来确定左右边界的初始值，即通过从左往右是否单调递增确定左边界初始值，通过从右往左是否单调递减确定右边界初始值。注意这里不是到这一步就结束了，比如nums数组为[2, 6, 4, 1, 12, 9, 10]，初始值确定了左边界为6，右边界为12，但是还需要调整，调整完毕的左边界为2，右边界为10，即整个数组；
    3. 从b步骤中确定好的左右区间开始遍历，目的是调整左右边界，使左边界向左、右边界向右调整，即满足中间子数组中的元素要大于左子数组、小于右子数组，期间需要不断维护 min（左边界对应的数组元素），max（右边界对应的数组元素），因为在遍历中间数组时需要将当前遍历的元素与min和max作比较；

    4. 遍历的过程中可能会到达数组的边缘，此时可以建立两个哨兵：数组下标为0的左边存一个足够小的数，数组下标为len - 1的右边存一个足够大的数，这样当到达数组边缘后，便不会再进入对应的if条件中了。

      41.3 代码

      排序数组：

      1. class Solution {
      2. public int findUnsortedSubarray(int[] nums) {
      3.   int len = nums.length;
      4.   int[] numsCopy = new int[len];
      5.   System.arraycopy(nums, 0, numsCopy, 0, len);
      6.   Arrays.sort(numsCopy);
      7.   int left = 0, right = len - 1;
      8.   // 始终需要保证left <= right
      9.   while (left <= right && numsCopy[left] == nums[left]) {
      10.       ++left;
      11.   }
      12.   while (left <= right && numsCopy[right] == nums[right]) {
      13.       --right;
      14.   }
      15.   return right - left + 1;
      16. }
      17. }

      双指针：

      1. class Solution {
      2. public int findUnsortedSubarray(int[] nums) {
      3.   int MIN = -100005, MAX = 100005;
      4.   int len = nums.length;
      5.   int i = 0, j = len - 1;
      6.   // 确定初始边界
      7.   while (i < j && nums[i] <= nums[i + 1]) {
      8.       ++i;
      9.   }
      10.   while (i < j && nums[j - 1] <= nums[j]) {
      11.       --j;
      12.   }
      13.   // 调整边界
      14.   // min为左边界对应的数组元素，max为右边界对应的数组元素
      15.   int min = nums[i], max = nums[j];
      16.   int left = i, right = j;
      17.   for (int index = left; index <= right; ++index) {
      18.       // 向左调整左边界
      19.       if (nums[index] < min) {
      20.           while (i >= 0 && nums[i] > nums[index]) {
      21.               --i;
      22.           }
      23.           min = i >= 0? nums[i]: MIN;
      24.       }
      25.       // 向右调整有边界
      26.       if (nums[index] > max) {
      27.           while (j < len && nums[j] < nums[index]) {
      28.               ++j;
      29.           }
      30.           max = j < len? nums[j]: MAX;
      31.       }
      32.   }
      34.   // 比如nums为[1, 2, 3, 4]，完全不需要调整，在左右边界初始化阶段，i == j
      35.   return i == j? 0: (j - 1) - (i + 1) + 1;
      36. }
      37. }

      42、88. 合并两个有序数组

      42.1 题目

      给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
      示例 1：

      输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出：[1,2,2,3,5,6] 解释：需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0 输出：[1] 解释：需要合并 [1] 和 [] 。 合并结果是 [1] 。

示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1 输出：[1] 解释：需要合并的数组是 [] 和 [1] 。 合并结果是 [1] 。 注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

42.2 思路

本题有两个思路：

  1. 从前向后遍历（时间复杂度O(m + n)，空间复杂度O(m + n)）：
    1. 用一个新数组，将排序后的元素先插入到新数组中，最后再将新数组中的元素复制到nums1中；
    2. 用两个指针分别指向nums1和nums2，判断哪个值小，就作为当前要插入新数组中的cur；
    3. 再用一个指针指向新数组中的下标并维护；
    4. 将新数组中的元素复制到nums1中。

  2. 从后向前遍历（时间复杂度O(m + n)，空间复杂度O(1)）：

    1. 如果想进一步降低空间复杂度，可以考虑直接在nums1数组上进行修改，如果从前向后遍历，可能会出现nums1数组中的元素还没被取出就被覆盖了，如何能让nums1数组中的元素不被覆盖呢？观察到nums1数组中的后半部分都是0，可以考虑从后向前遍历；
    2. 维护三个指针：p1指向nums1数组末尾，p2指向nums2数组末尾，index指向被重新赋值的nums1数组的末尾；
    3. 比较nums1[p1]和nums2[p2]，将较大值优先插入index指向的地方；

    4. 如何证明p1后面的位置永远足够容纳被插入的元素，不会产生p1的元素被覆盖的情况呢？

      1.     ![image.png](https://cdn.nlark.com/yuque/0/2022/png/1536187/1655046936766-db443f4e-9cc8-4145-a845-df4af2558335.png#clientId=ub148ffab-147e-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=250&id=uf732b152&margin=%5Bobject%20Object%5D&name=image.png&originHeight=333&originWidth=975&originalType=binary&ratio=1&rotation=0&showTitle=false&size=36280&status=done&style=none&taskId=ue9e9deb0-1291-44f2-8ed0-d87ba19694c&title=&width=731)

      42.3 代码

      从前向后遍历：

      1. class Solution {
      2. public void merge(int[] nums1, int m, int[] nums2, int n) {
      3.   int p1 = 0, p2 = 0, index = 0;
      4.   int cur;
      5.   int[] sorted = new int[m + n];
      6.   while (p1 < m || p2 < n) {
      7.       if (p1 == m) {
      8.           cur = nums2[p2++];
      9.       } else if (p2 == n) {
      10.           cur = nums1[p1++];
      11.       } else if (nums1[p1] < nums2[p2]) {
      12.           cur = nums1[p1++];
      13.       } else {
      14.           cur = nums2[p2++];
      15.       }
      16.       sorted[index++] = cur;
      17.   }
      19.   for (int i = 0; i < sorted.length; ++i) {
      20.       nums1[i] = sorted[i];
      21.   }
      22. }
      23. }

      从后向前遍历：

      1. class Solution {
      2. public void merge(int[] nums1, int m, int[] nums2, int n) {
      3.   int p1 = m - 1, p2 = n - 1, index = m + n - 1;
      4.   int cur;
      5.   while (p1 >= 0 || p2 >= 0) {
      6.       if (p1 == -1) {
      7.           cur = nums2[p2--];
      8.       } else if (p2 == -1) {
      9.           cur = nums1[p1--];
      10.       } else if (nums1[p1] > nums2[p2]) {
      11.           cur = nums1[p1--];
      12.       } else {
      13.           cur = nums2[p2--];
      14.       }
      15.       nums1[index--] = cur;
      16.   }
      17. }
      18. }