一.前缀和数组(小而美算法技巧)

1.区域和检索-数组不可变

⼀维数组中的前缀和 先看⼀道例题，⼒扣第 303 题「区域和检索 - 数组不可变」，让你计算数组区间内元素的和，这是⼀道标准 的前缀和问题 。
没使用前缀和
sumRange 函数需要计算并返回⼀个索引区间之内的元素和，没学过前缀和的⼈可能写出如下代码：

  1. class NumArray {
  2.     private int[] nums;
  3.     public NumArray(int[] nums) {
  4.         this.nums=nums;
  5.     }
  7.     public int sumRange(int left, int right) {
  8.         int res=0;
  9.         for(int i=left;i<=right;i++){
  10.             res+=nums[i];
  11.         }
  12.         return res;
  13.     }
  14. }

题解:
基本思路
标准的前缀和问题，核心思路是用一个新的数组 preSum 记录 nums[0..i-1] 的累加和，看图 10 = 3 + 5 + 2
还等于8+2=10。
一丶数组和链表 - 图3
看这个 preSum 数组，如果我想求索引区间 [1, 4] 内的所有元素之和，就可以通过 preSum[5] - preSum[1] 得出。
这样，sumRange 函数仅仅需要做一次减法运算，避免了每次进行 for 循环调用，最坏时间复杂度为常数 O(1)。

  1. class NumArray {
  2.     // 前缀和数组
  3.     private int[] preSum;
  5.     /* 输入一个数组，构造前缀和 */
  6.     public NumArray(int[] nums) {
  7.         // preSum[0] = 0，便于计算累加和
  8.         preSum = new int[nums.length + 1];
  9.         // 计算 nums 的累加和
  10.         for (int i = 1; i < preSum.length; i++) {
  11.             preSum[i] = preSum[i - 1] + nums[i - 1];
  12.         }
  13.     }
  15.     /* 查询闭区间 [left, right] 的累加和 */
  16.     public int sumRange(int left, int right) {
  17.         return preSum[right + 1] - preSum[left];
  18.     }
  19. }

2.二维区域和检索–矩阵不可变

这是力扣第304题「304.二维区域和检索–矩阵不可变」，其实和上一题类似，上一题是让你计算子数组的元素之和，这道题让你计算二维矩阵中子矩阵的元素之和:

一丶数组和链表 - 图4image.png

如果我想计算红色的这个子矩阵的元素之和，可以用绿色矩阵减去蓝色矩阵减去橙色矩阵最后加上粉色矩阵，而绿蓝橙粉这四个矩阵有一个共同的特点，就是左上角就是 (0, 0) 原点。

那么我们可以维护一个二维 preSum 数组，专门记录以原点为顶点的矩阵的元素之和，就可以用几次加减运算算出任何一个子矩阵的元素和。

运用:注意我们构造的二维数组外圈围个0就可以减少很多判断了
例如：1.如果我们要计算下面123246369不在外面围个0是不行的。
image.png ![C)@XDEVD8V2N@NF91OQQ$6.png

  1. class NumMatrix {
  2.     // preSum[i][j] 记录矩阵 [0, 0, i, j] 的元素和
  3.     private int[][] preSum;
  5.     public NumMatrix(int[][] matrix) {
  6.         int m = matrix.length, n = matrix[0].length;
  7.         if (m == 0 || n == 0) return;
  8.         // 构造前缀和矩阵
  9.         preSum = new int[m + 1][n + 1];
  10.         for (int i = 1; i <= m; i++) {
  11.             for (int j = 1; j <= n; j++) {
  12.                 // 计算每个矩阵 [0, 0, i, j] 的元素和
  13.                 preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] + matrix[i - 1][j - 1] - preSum[i-1][j-1];
  14.             }
  15.         }
  16.     }
  18.     // 计算子矩阵 [x1, y1, x2, y2] 的元素和
  19.     public int sumRegion(int x1, int y1, int x2, int y2) {
  20.         // 目标矩阵之和由四个相邻矩阵运算获得
  21.         return preSum[x2+1][y2+1] - preSum[x1][y2+1] - preSum[x2+1][y1] + preSum[x1][y1];
  22.     }
  23. }

3.和为 k 的⼦数组

最后聊⼀道稍微有些困难的前缀和题⽬，⼒扣第 560 题「和为 K 的⼦数组].
image.png
解法一:(枚举法)

  1. int subarraySum(int[] nums, int k) {
  2.      int n = nums.length;
  3.      // 构造前缀和
  4.      int[] preSum = new int[n + 1];
  5.     preSum[0] = 0; 
  6.      for (int i = 0; i < n; i++)
  7.      preSum[i + 1] = preSum[i] + nums[i];
  9.      int res = 0;
  10.      // 穷举所有⼦数组
  11.      for (int i = 1; i <= n; i++)
  12.          for (int j = 0; j < i; j++)
  13.          // ⼦数组 nums[j..i-1] 的元素和
  14.      if (preSum[i] - preSum[j] == k)
  15.          res++;
  16.      return res;
  17. }

image.png

解法二(利用HashMap)
这个解法的时间复杂度 O(N^2) 空间复杂度 O(N)，并不是最优的解法。不过通过这个解法理解了前缀和数 组的⼯作原理之后，可以使⽤⼀些巧妙的办法把时间复杂度进⼀步降低。 注意前⾯的解法有嵌套的 for 循环： 

  1. for (int i = 1; i <= n; i++)
  2.  for (int j = 0; j < i; j++)
  3.  if (preSum[i] - preSum[j] == k)
  4.  res++;

第⼆层 for 循环在⼲嘛呢？翻译⼀下就是，在计算，有⼏个 j 能够使得 preSum[i] 和 preSum[j] 的差为 k。毎找到⼀个这样的 j，就把结果加⼀。 我们可以把 if 语句⾥的条件判断移项，这样写：

  1. if (preSum[j] == preSum[i] - k)
  2.  res++;

优化的思路是：我直接记录下有⼏个 preSum[j] 和 preSum[i] - k 相等，直接更新结果，就避免了内层 的 for 循环。我们可以⽤哈希表，在记录前缀和的同时记录该前缀和出现的次数。 

  1. class Solution {
  2.     public int subarraySum(int[] nums, int k) {
  3.         int n = nums.length;
  4.         // map：前缀和 -> 该前缀和出现的次数
  5.         HashMap<Integer, Integer> 
  6.             preSum = new HashMap<>();
  7.         // base case
  8.         preSum.put(0, 1);
  10.         int res = 0, sum0_i = 0;
  11.         for (int i = 0; i < n; i++) {
  12.             sum0_i += nums[i];
  13.             // 这是我们想找的前缀和 nums[0..j]
  14.             int sum0_j = sum0_i - k;
  15.             // 如果前面有这个前缀和，则直接更新答案
  16.             if (preSum.containsKey(sum0_j))
  17.                 res += preSum.get(sum0_j);
  18.             // 把前缀和 nums[0..i] 加入并记录出现次数
  19.             preSum.put(sum0_i, 
  20.                 preSum.getOrDefault(sum0_i, 0) + 1);
  21.         }
  22.         return res;
  23.     }
  24. }

⽐如说下⾯这个情况，需要前缀和 8 就能找到和为 k 的⼦数组了，之前的暴⼒解法需要遍历数组去数有⼏个 8，⽽优化解法借助哈希表可以直接得知有⼏个前缀和为 8。
image.png
这样，就把时间复杂度降到了 O(N)，是最优解法了。 前缀和技巧就讲到这⾥，应该说这个算法技巧是会者不难难者不会，实际运⽤中还是要多培养⾃⼰的思维灵 活性，做到⼀眼看出题⽬是⼀个前缀和问题。

二、差分数组(小而美的算法技巧)

介绍

差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。
这里就需要差分数组的技巧，类似前缀和技巧构造的 prefix 数组，我们先对 nums 数组构造一个 diff 差分数组，diff[i] 就是 nums[i] 和 nums[i-1] 之差：

  1. int[] diff = new int[nums.length];
  2. // 构造差分数组
  3. diff[0] = nums[0];
  4. for (int i = 1; i < nums.length; i++) {
  5.     diff[i] = nums[i] - nums[i - 1];
  6. }

一丶数组和链表 - 图10
通过这个 diff 差分数组是可以反推出原始数组 nums 的，代码逻辑如下：

  1. int[] res = new int[diff.length];
  2. // 根据差分数组构造结果数组
  3. res[0] = diff[0];
  4. for (int i = 1; i < diff.length; i++) {
  5.     res[i] = res[i - 1] + diff[i];
  6. }

这样构造差分数组 diff，就可以快速进行区间增减的操作，如果你想对区间 nums[i..j] 的元素全部加 3，那么只需要让 diff[i] += 3，然后再让 diff[j+1] -= 3 即可：
一丶数组和链表 - 图11
原理很简单，回想 diff 数组反推 nums 数组的过程，diff[i] += 3 意味着给 nums[i..] 所有的元素都加了 3，然后 diff[j+1] -= 3 又意味着对于 nums[j+1..] 所有元素再减 3，那综合起来，是不是就是对 nums[i..j] 中的所有元素都加 3 了？
只要花费 O(1) 的时间修改 diff 数组，就相当于给 nums 的整个区间做了修改。多次修改 diff，然后通过 diff 数组反推，即可得到 nums 修改后的结果。
现在我们把差分数组抽象成一个类，包含 increment 方法和 result 方法：

  1. // 差分数组工具类
  2. class Difference {
  3.     // 差分数组
  4.     private int[] diff;
  6.     /* 输入一个初始数组，区间操作将在这个数组上进行 */
  7.     public Difference(int[] nums) {
  8.         assert nums.length > 0;
  9.         diff = new int[nums.length];
  10.         // 根据初始数组构造差分数组
  11.         diff[0] = nums[0];
  12.         for (int i = 1; i < nums.length; i++) {
  13.             diff[i] = nums[i] - nums[i - 1];
  14.         }
  15.     }
  17.     /* 给闭区间 [i,j] 增加 val（可以是负数）*/
  18.     public void increment(int i, int j, int val) {
  19.         diff[i] += val;
  20.         if (j + 1 < diff.length) {
  21.             diff[j + 1] -= val;
  22.         }
  23.     }
  25.     /* 返回结果数组 */
  26.     public int[] result() {
  27.         int[] res = new int[diff.length];
  28.         // 根据差分数组构造结果数组
  29.         res[0] = diff[0];
  30.         for (int i = 1; i < diff.length; i++) {
  31.             res[i] = res[i - 1] + diff[i];
  32.         }
  33.         return res;
  34.     }
  35. }

这⾥注意⼀下 increment ⽅法中的 if 语句： 

  1. public void increment(int i, int j, int val) {
  2.      diff[i] += val;
  3.      if (j + 1 < diff.length) {
  4.          diff[j + 1] -= val;
  5.      }
  6. }

当 j+1 >= diff.length 时，说明是对 nums[i] 及以后的整个数组都进⾏修改，那么就不需要再给 diff 数组减 val 了。

1.区间加法

CL}93U_QK74V]$US)_{(81A.png
那么我们直接复⽤刚才实现的 Difference 类就能把这道题解决掉： 

  1. int[] getModifiedArray(int length, int[][] updates) {
  2.      // nums 初始化为全 0
  3.      int[] nums = new int[length];
  4.      // 构造差分解法
  5.      Difference df = new Difference(nums);
  7.      for (int[] update : updates) {
  8.      int i = update[0];
  9.      int j = update[1];
  10.      int val = update[2];
  11.      df.increment(i, j, val);
  12.  }
  13.    return df.result();
  14. }

2.航班预订统计(1109)

image.png
示例

  1. 输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
  2. 输出：[10,55,45,25,25]
  3. 解释：
  4. 航班编号        1   2   3   4   5
  5. 预订记录 1 ：   10  10
  6. 预订记录 2 ：       20  20
  7. 预订记录 3 ：       25  25  25  25
  8. 总座位数：      10  55  45  25  25
  9. 因此，answer = [10,55,45,25,25]

我给你翻译⼀下： 给你输⼊⼀个⻓度为 n 的数组 nums，其中所有元素都是 0。再给你输⼊⼀个 bookings，⾥⾯是若⼲三元组 (i,j,k)，每个三元组的含义就是要求你给 nums 数组的闭区间 [i-1,j-1] 中所有元素都加上 k。请你返 回最后的 nums 数组是多少？

PS：因为题⽬说的 n 是从 1 开始计数的，⽽数组索引从 0 开始，所以对于输⼊的三元组 (i,j,k)， 数组区间应该对应 [i-1,j-1]。 

  1. int[] corpFlightBookings(int[][] bookings, int n) {
  2.      // nums 初始化为全 0
  3.        int[] nums = new int[n];
  4.        // 构造差分解法
  5.        Difference df = new Difference(nums);
  6.      for (int[] booking : bookings) {
  7.      // 注意转成数组索引要减⼀哦
  8.        int i = booking[0] - 1;
  9.        int j = booking[1] - 1;
  10.        int val = booking[2];
  11.      // 对区间 nums[i..j] 增加 val
  12.      df.increment(i, j, val);
  13.    }
  14.      // 返回最终的结果数组
  15.      return df.result();
  16. }

三、滑动窗口算法

介绍

滑动窗⼝算法的代码框架 

  1. /* 滑动窗⼝算法框架 */
  2. class Solution {
  3.     public String minWindow(String s, String t) {
  4.         HashMap<Character,Integer> need = new HashMap<>();
  5.         HashMap<Character,Integer> window = new HashMap<>();
  6.         for(char ch : t.toCharArray()){
  7.             need.put(ch,need.getOrDefault(ch,0) + 1);
  8.         }
  9.          int left =0;  int right=0;
  10.             int valid=0;
  11.         while(right < s.length()){
  12.             // c 是将移⼊窗⼝的字符
  13.             char c = s.charAt(right);
  14.             // 右移窗⼝
  15.             right++;
  16.             // 进⾏窗⼝内数据的⼀系列更新
  17.                 .........
  19.              /*** debug 输出的位置 ***/
  20.              printf("window: [%d, %d)\n", left, right);
  21.              /********************/
  23.           // 判断左侧窗⼝是否要收缩
  24.             while(valid == need.size()){
  25.                // d 是将移出窗⼝的字符
  26.                 char d = s.charAt(left);
  27.                 // 左移窗⼝
  28.                 left++;
  29.        // 进⾏窗⼝内数据的⼀系列更新
  30.             .................
  31.               }
  32.            }
  33.     }
  34. }

其中两处 … 表示的更新窗⼝数据的地⽅，到时候你直接往⾥⾯填就⾏了。

1.最⼩覆盖⼦串 (76)

image.png

2.滑动窗口思路:

滑动窗⼝算法的思路是这样：
1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」。
2、我们先不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。
3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。
4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。
这个思路其实也不难，第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解，也就是最短的覆盖子串。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动，这就是「滑动窗口」这个名字的来历。
下面画图理解一下，needs 和 window 相当于计数器，分别记录 T 中字符出现次数和「窗口」中的相应字符的出现次数。
初始状态：
一丶数组和链表 - 图15
增加 right，直到窗口 [left, right] 包含了 T 中所有字符：
一丶数组和链表 - 图16
现在开始增加 left，缩小窗口 [left, right]：
一丶数组和链表 - 图17
直到窗口中的字符串不再符合要求，left 不再继续移动：
一丶数组和链表 - 图18
之后重复上述过程，先移动 right，再移动 left…… 直到 right 指针到达字符串 S 的末端，算法结束。
如果你能够理解上述过程，恭喜，你已经完全掌握了滑动窗口算法思想。现在我们来看看这个滑动窗口代码框架怎么用：

  1. class Solution {
  2.     public String minWindow(String s, String t) {
  3.         HashMap<Character,Integer> need = new HashMap<>();
  4.         HashMap<Character,Integer> window = new HashMap<>();
  5.         for(char ch : t.toCharArray()){
  6.             need.put(ch,need.getOrDefault(ch,0) + 1);
  7.         } 
  8.         int left = 0;
  9.         int right = 0;
  10.         int valid = 0;
  11.         int start = 0;
  12.         int len = Integer.MAX_VALUE;
  13.         while(right < s.length()){
  14.             char c = s.charAt(right);
  15.             right++;
  16.             // 返回最⼩覆盖⼦串
  17.             if(need.containsKey(c)){            
  18.                 window.put(c,window.getOrDefault(c,0) + 1);
  19.                 ////这个得改成equals
  20.                 if(window.get(c).equals(need.get(c))){
  21.                     valid++;
  22.                                   }                                                                                                                      
  23.             }
  24.             // 判断左侧窗⼝是否要收缩
  25.             while(valid == need.size()){
  26.                 // 在这⾥更新最⼩覆盖⼦串
  27.                 if(right - left < len){
  28.                     start = left;
  29.                     len = right - left;
  30.                 }
  31.                 // d 是将移出窗⼝的字符
  32.                 char d = s.charAt(left);
  33.                 // 左移窗⼝
  34.                 left++;
  35.                 // 进⾏窗⼝内数据的⼀系列更新
  36.                 if(need.containsKey(d)){
  37.                     if(window.get(d).equals(need.get(d))){
  38.                         valid--; 
  39.                     }
  40.                     window.put(d,window.getOrDefault(d,0) - 1);
  41.                 }
  42.             }
  43.         }
  44.         // 返回最⼩覆盖⼦串
  45.         return len == Integer.MAX_VALUE ? "" : s.substring(start,start + len);
  46.     }
  47. }

套模板，只需要思考以下四个问题：
1、当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？
2、什么条件下，窗口应该暂停扩大，开始移动 left 缩小窗口？
3、当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？
4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？
如果一个字符进入窗口，应该增加 window 计数器；如果一个字符将移出窗口的时候，应该减少 window 计数器；当 valid 满足 need 时应该收缩窗口；应该在收缩窗口的时候更新最终结果。

2.字符串排列(567)

D_%@QY%RTJ9I()7L9JFIIRE.png
注意哦，输⼊的 s1 是可以包含重复字符的，所以这个题难度不⼩。
这种题⽬，是明显的滑动窗⼝算法，相当给你⼀个 S 和⼀个 T，请问你 S 中是否存在⼀个⼦串，包含 T 中所有字符且不包含其他字符？

  1. class Solution {
  2.     // 判断 s 中是否存在 t 的排列
  3.     public boolean checkInclusion(String t, String s) {
  4.         HashMap<Character,Integer> need = new HashMap<>();
  5.         HashMap<Character,Integer> window = new HashMap<>();
  6.         for(char ch : t.toCharArray()){
  7.             need.put(ch,need.getOrDefault(ch,0) + 1);
  8.         }
  10.         int left =0;  int right=0;
  11.             int valid=0;
  12.         while(right < s.length()){
  13.             char c = s.charAt(right);
  14.             right++;
  15.             // 进⾏窗⼝内数据的⼀系列更新
  16.              if(need.containsKey(c)){            
  17.                 window.put(c,window.getOrDefault(c,0) + 1);
  18.                 if(window.get(c).equals(need.get(c))){
  19.                     valid++;                   
  20.                 }                                                                                                                      
  21.             }
  23.             // 判断左侧窗⼝是否要收缩
  24.         while (right - left >= t.length()) {
  25.             // 在这⾥判断是否找到了合法的⼦串
  26.             if (valid == need.size()){
  27.                 return true;
  28.             }
  29.                 char d = s.charAt(left);
  30.                 left++;
  31.             // 进⾏窗⼝内数据的⼀系列更新
  32.                 if(need.containsKey(d)){
  33.                     if(window.get(d).equals(need.get(d))){
  34.                         valid--; 
  35.                     }
  36.                     window.put(d,window.getOrDefault(d,0) - 1);
  37.                 }
  38.     }
  40. }
  41.     // 未找到符合条件的⼦串
  42.         return false;
  43.     }
  44. }

帮助理解的
image.png
对于这道题的解法代码，基本上和最⼩覆盖⼦串⼀模⼀样，只需要改变两个地⽅：
1、本题移动 left 缩⼩窗⼝的时机是窗⼝⼤⼩⼤于 t.size() 时，应为排列嘛，显然⻓度应该是⼀样的。
2、当发现 valid == need.size() 时，就说明窗⼝中就是⼀个合法的排列，所以⽴即返回 true。
⾄于如何处理窗⼝的扩⼤和缩⼩，和最⼩覆盖⼦串完全相同。

PS：由于这道题中 [left, right) 其实维护的是一个定长的窗口，窗口大小为 t.size()。因为定长窗口每次向前滑动时只会移出一个字符，所以可以把内层的 while 改成 if，效果是一样的。

3.找到字符串中所有字母异位词(438)

image.png
呵呵，这个所谓的字⺟异位词，不就是排列吗，搞个⾼端的说法就能糊弄⼈了吗？相当于，输⼊⼀个串 S， ⼀个串 T，找到 S 中所有 T 的排列，返回它们的起始索引。 

  1. class Solution {
  2.     public List<Integer> findAnagrams(String s, String t) {
  3.  HashMap<Character,Integer> need = new HashMap<>();
  4.         HashMap<Character,Integer> window = new HashMap<>();
  5.         for(char ch : t.toCharArray()){
  6.             need.put(ch,need.getOrDefault(ch,0) + 1);
  7.         }
  9.         int left =0;  int right=0;
  10.             int valid=0;
  11.             List<Integer> res = new ArrayList<>();
  12.         while(right < s.length()){
  13.             char c = s.charAt(right);
  14.             right++;
  15.             // 进⾏窗⼝内数据的⼀系列更新
  16.              if(need.containsKey(c)){            
  17.                 window.put(c,window.getOrDefault(c,0) + 1);
  18.                 if(window.get(c).equals(need.get(c))){
  19.                     valid++;                                     }                                                                                                                      
  20.             }
  22.             // 判断左侧窗⼝是否要收缩
  23.         while (right - left >= t.length()) {
  24.             // 在这⾥判断是否找到了合法的⼦串
  25.             if (valid == need.size()){
  26.                  res.add(left);
  27.             }
  28.                 char d = s.charAt(left);
  29.                 left++;
  30.             // 进⾏窗⼝内数据的⼀系列更新
  31.                 if(need.containsKey(d)){
  32.                     if(window.get(d).equals(need.get(d))){
  33.                         valid--; 
  34.                     }
  35.                     window.put(d,window.getOrDefault(d,0) - 1);
  36.                 }
  37.     }
  39. }
  40.     // 未找到符合条件的⼦串
  41.         return res;
  42.     }
  43. }

跟寻找字符串的排列⼀样，只是找到⼀个合法异位词（排列）之后将起始索引加⼊ res 即可。

4.最⻓⽆重复⼦串(3)

image.png
这个题终于有了点新意，不是⼀套框架就出答案，不过反⽽更简单了，稍微改⼀改框架就⾏了：

  1. class Solution {
  2.     public int lengthOfLongestSubstring(String s) {
  4.         HashMap<Character,Integer> window = new HashMap<>();
  6.          int left =0;  int right=0;
  7.             int res=0;
  9.         while(right < s.length()){
  10.             // c 是将移⼊窗⼝的字符
  11.             char c = s.charAt(right);
  12.             // 右移窗⼝
  13.             right++;
  15.          window.put(c,window.getOrDefault(c,0) + 1);
  17.           // 判断左侧窗⼝是否要收缩
  18.             while(window.get(c)>1){
  19.                // d 是将移出窗⼝的字符
  20.                 char d = s.charAt(left);
  21.                 // 左移窗⼝
  22.                 left++;
  24.                  window.put(d,window.getOrDefault(d,0) - 1);
  26.               }
  27.               res=Math.max(res,right-left);
  28.            }
  29.    return  res;
  31.     }
  32. }

帮助理解
image.png

四、二分法

1.二分法框架

  1. int binarySearch(int[] nums, int target) {
  2.      int left = 0, right = ...;
  3. while(...) {
  4.      int mid = left + (right - left) / 2;
  5.      if (nums[mid] == target) {
  6.              ...
  7.      } else if (nums[mid] < target) {
  8.              left = ...
  9.      } else if (nums[mid] > target) {
  10.              right = ...
  11.      }
  12.   }
  13.      return ...;
  14. }

技巧1:不要出现 else，⽽是把所有情况⽤ else if 写清楚，这样可以清楚地展现所有细
节。
技巧2:计算 mid 时需要防⽌溢出，代码中 left + (right - left) / 2 就和 (left + right) / 2 的结果相同，但是有效防⽌了 left 和 right 太⼤直接相加导致溢出。

2.寻找一个数(基本的二分搜索)

即搜索⼀个数，如果存在，返回其索引，否则返回 -1。

  1. int binarySearch(int[] nums, int target) {
  2.      int left = 0; 
  3.      int right = nums.length - 1; // 注意.
  5.  while(left <= right) {
  6.      int mid = left + (right - left) / 2;
  7.      if(nums[mid] == target)
  8.              return mid; 
  9.      else if (nums[mid] < target)
  10.              left = mid + 1; // 注意
  11.      else if (nums[mid] > target)
  12.              right = mid - 1; // 注意
  13.      }
  14.  return -1; 
  15. }

注意1: 初始化 right 的赋值是 nums.length - 1, 所以是left<=right,初始化 right 的赋值是 nums.length,是left<right 。

注意2: 没有找到 需要终止while循环,然后返回-1。
while(left <= right) 的终⽌条件是 left == right + 1，写成区间的形式就是 [right + 1, right]，或者带个具体的数字进去 [3, 2]，可⻅这时候区间为空，因为没有数字既⼤于等于 3 ⼜⼩于等于 2 的吧。所以这时候 while 循环终⽌是正确的，直接返回 -1 即可。
while(left < right) 的终⽌条件是 left == right，写成区间的形式就是 [right, right]，或者带个具体的数字进去 [2, 2]，这时候区间⾮空，还有⼀个数 2，但此时 while 循环终⽌了。也就是说这区间 [2, 2] 被漏掉了，索引 2 没有被搜索，如果这时候直接返回 -1 就是错误的。
当然，如果你⾮要⽤ while(left < right) 也可以，我们已经知道了出错的原因，就打个补丁好了：

  1. //...
  2.  while(left < right) {
  3.      // ...
  4.  }
  5.  return nums[left] == target ? left : -1;

注意3:为什么 left = mid + 1，right = mid - 1？我看有的代码是 right = mid 或者 left = mid,没有这些加加减减，到底怎么回事，怎么判断？
答：这也是⼆分查找的⼀个难点，不过只要你能理解前⾯的内容，就能够很容易判断。 刚才明确了「搜索区间」这个概念，⽽且本算法的搜索区间是两端都闭的，即 [left, right]。那么当我 们发现索引 mid 不是要找的 target 时，下⼀步应该去搜索哪⾥呢?当然是去搜索 [left, mid-1] 或者 [mid+1, right] 对不对？因为 mid 已经搜索过，应该从搜索区间中去除。

3、此算法有什么缺陷？
答：⾄此，你应该已经掌握了该算法的所有细节，以及这样处理的原因。但是，这个算法存在局限性。

⽐如说给你有序数组 nums = [1,2,2,2,3]，target 为 2，此算法返回的索引是 2，没错。但是如果我想
得到 target 的左侧边界，即索引 1，或者我想得到 target 的右侧边界，即索引 3，这样的话此算法是⽆法处理的。

这样的需求很常⻅，你也许会说，找到⼀个 target，然后向左或向右线性搜索不⾏吗？可以，但是不好，因为这样难以保证⼆分查找对数级的复杂度了。

我们后续的算法就来讨论这两种⼆分查找的算法。

3.寻找左侧边界的⼆分搜索

  1. int left_bound(int[] nums, int target) {
  2.      int left = 0, right = nums.length - 1;
  3.  // 搜索区间为 [left, right]
  4.      while (left <= right) {
  5.          int mid = left + (right - left) / 2;
  6.          if (nums[mid] < target) {
  7.              // 搜索区间变为 [mid+1, right]
  8.              left = mid + 1;
  9.          } else if (nums[mid] > target) {
  10.              // 搜索区间变为 [left, mid-1]
  11.              right = mid - 1;
  12.          } else if (nums[mid] == target) {
  13.              // 收缩右侧边界
  14.              right = mid - 1;
  15.          }
  16.  }
  17.  // 检查出界情况
  18.  if (left >= nums.length || nums[left] != target)
  19.          return -1;
  20.  return left;
  21. }

注意1:由于 while 的退出条件是 left == right + 1，所以当 target ⽐ nums 中所有元素都⼤时，会存在以下情况使得索引越界：
image.png

4.寻找右侧边界的⼆分查找

  1. int right_bound(int[] nums, int target) {
  2.     int left = 0, right = nums.length - 1;
  3.     while (left <= right) {
  4.         int mid = left + (right - left) / 2;
  5.         if (nums[mid] < target) {
  6.             left = mid + 1;
  7.         } else if (nums[mid] > target) {
  8.             else if (nums[mid] == target) {
  9.                 // 这⾥改成收缩左侧边界即可
  10.                 left = mid + 1;
  11.             }
  12.         }
  13.         // 这⾥改为检查 right 越界的情况，⻅下图
  14.         if (right < 0 || nums[right] != target)
  15.             return -1;
  16.         return right;
  17. }

当 target ⽐所有元素都⼩时，right 会被减到 -1，所以需要在最后防⽌越界：
image.png

二分搜索题型套路分析(暂定)

五、田忌赛马背后的算法决策(暂定)

六、⼀⽂秒杀四道原地修改数组的算法题

删除排序数组中的重复项(26)

image.png
image.png
简单解释⼀下什么是原地修改：
如果不是原地修改的话，我们直接 new ⼀个 int[] 数组，把去重之后的元素放进这个新数组中，然后返回
这个新数组即可。但是原地删除，不允许我们 new 新数组，只能在原数组上操作，然后返回⼀个⻓度，这样就可以通过返回的⻓度和原始数组得到我们去重后的元素有哪些了。

我们让慢指针 slow ⾛在后⾯，快指针 fast ⾛在前⾯探路，找到⼀个不重复的元素就告诉 slow 并让 slow
前进⼀步。这样当 fast 指针遍历完整个数组 nums 后，nums[0..slow] 就是不重复元素。

  1. class Solution {
  2.     public int removeDuplicates(int[] nums) {
  3.         if (nums.length == 0) {
  4.             return 0;
  5.         }
  6.         int slow = 0, fast = 0;
  7.         while (fast < nums.length) {
  8.             if (nums[fast] != nums[slow]) {
  9.                 slow++;
  10.                 // 维护 nums[0..slow] 无重复
  11.                 nums[slow] = nums[fast];
  12.             }
  13.             fast++;
  14.         }
  15.         // 数组长度为索引 + 1
  16.         return slow + 1;
  17.     }
  18. }

一丶数组和链表 - 图28

删除排序链表中的重复元素(83)

image.png

  1. class Solution {
  2.     public deleteDuplicates(ListNode head) {
  3.         if (head == null) return null;
  4.         ListNode slow = head, fast = head;
  5.         while (fast != null) {
  6.             if (fast.val != slow.val) {
  7.                 // nums[slow] = nums[fast];
  8.                 slow.next = fast;
  9.                 // slow++;
  10.                 slow = slow.next;
  11.             }
  12.             // fast++
  13.             fast = fast.next;
  14.         }
  15.         // 断开与后面重复元素的连接
  16.         slow.next = null;
  17.         return head;
  18.     }
  19. }

一丶数组和链表 - 图30

移除元素(27)

image.png
image.png
题⽬要求我们把 nums 中所有值为 val 的元素原地删除，依然需要使⽤ 双指针技巧 中的快慢指针：
如果 fast 遇到需要去除的元素，则直接跳过，否则就告诉 slow 指针，并让 slow 前进⼀步。
这和前⾯说到的数组去重问题解法思路是完全⼀样的，就不画 GIF 了，直接看代码：

  1. int removeElement(int[] nums, int val) {
  2.     int fast = 0, slow = 0;
  3.     while (fast < nums.length) {
  4.         if (nums[fast] != val) {
  5.             nums[slow] = nums[fast];
  6.             slow++;
  7.         }
  8.         fast++;
  9.     }
  10.     return slow;
  11. }

注意这⾥和有序数组去重的解法有⼀个重要不同，我们这⾥是先给 nums[slow] 赋值然后再给 slow++，这
样可以保证 nums[0..slow-1] 是不包含值为 val 的元素的，最后的结果数组⻓度就是 slow。

移动零(283)

image.png

  1. class Solution {
  2.     public void moveZeroes(int[] nums) {
  3.         // 去除 nums 中的所有 0
  4.         // 返回去除 0 之后的数组长度
  5.         int p = removeElement(nums, 0);
  6.         // 将 p 之后的所有元素赋值为 0
  7.         for (; p < nums.length; p++) {
  8.             nums[p] = 0;
  9.         }
  10.     }
  12.     // 双指针技巧，复用 [27. 移除元素] 的解法。
  13.     int removeElement(int[] nums, int val) {
  14.         int fast = 0, slow = 0;
  15.         while (fast < nums.length) {
  16.             if (nums[fast] != val) {
  17.                 nums[slow] = nums[fast];
  18.                 slow++;
  19.             }
  20.             fast++;
  21.         }
  22.         return slow;
  23.     }
  24. }

七、 ⼀⽂搞懂单链表的六⼤解题套路

合并两个有序链表(21)

image.png

  1. class Solution {
  2.     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
  3.         // 虚拟头结点
  4.         ListNode dummy = new ListNode(-1), p = dummy;
  5.         ListNode p1 = l1, p2 = l2;
  7.         while (p1 != null && p2 != null) {
  8.             // 比较 p1 和 p2 两个指针
  9.             // 将值较小的的节点接到 p 指针
  10.             if (p1.val > p2.val) {
  11.                 p.next = p2;
  12.                 p2 = p2.next;
  13.             } else {
  14.                 p.next = p1;
  15.                 p1 = p1.next;
  16.             }
  17.             // p 指针不断前进
  18.             p = p.next;
  19.         }
  21.         if (p1 != null) {
  22.             p.next = p1;
  23.         }
  24.         //技巧:p.next=p2  是把7-8都 放过去
  25.         if (p2 != null) {
  26.             p.next = p2;
  27.         }
  29.         return dummy.next;
  30.     }
  31. }

一丶数组和链表 - 图35

这个算法的逻辑类似于「拉拉链」，l1, l2 类似于拉链两侧的锯齿，指针 p 就好像拉链的拉索，将两个有序链表合并。
代码中还用到一个链表的算法题中是很常见的「虚拟头结点」技巧，也就是 dummy 节点，它相当于是个占位符，可以避免处理空指针的情况，降低代码的复杂性。

合并K个升序链表(23)(暂定)

单链表的倒数第 k 个节点

从前往后寻找单链表的第 k 个节点很简单，⼀个 for 循环遍历过去就找到了，但是如何寻找从后往前数的第 k 个节点呢？

那你可能说，假设链表有 n 个节点，倒数第 k 个节点就是正数第 n - k 个节点，不也是⼀个 for 循环的事⼉吗？

是的，但是算法题⼀般只给你⼀个 ListNode 头结点代表⼀条单链表，你不能直接得出这条链表的⻓度 n，⽽需要先遍历⼀遍链表算出 n 的值，然后再遍历链表计算第 n - k 个节点。

也就是说，这个解法需要遍历两次链表才能得到出倒数第 k 个节点。

那么，我们能不能只遍历⼀次链表，就算出倒数第 k 个节点？可以做到的，如果是⾯试问到这道题，⾯试官肯定也是希望你给出只需遍历⼀次链表的解法。

这个解法就⽐较巧妙了，假设 k = 2，思路如下：
⾸先，我们先让⼀个指针 p1 指向链表的头节点 head，然后⾛ k 步：
image.png
现在的 p1，只要再⾛ n - k 步，就能⾛到链表末尾的空指针了对吧？
趁这个时候，再⽤⼀个指针 p2 指向链表头节点 head：
image.png
接下来就很显然了，让 p1 和 p2 同时向前⾛，p1 ⾛到链表末尾的空指针时⾛了 n - k 步，p2 也⾛了 n -
k 步，也就是链表的倒数第 k 个节点：
image.png
这样，只遍历了⼀次链表，就获得了倒数第 k 个节点 p2。
上述逻辑的代码如下：

  1. // 返回链表的倒数第 k 个节点
  2. ListNode findFromEnd(ListNode head, int k) {
  3.  ListNode p1 = head;
  4.  // p1 先⾛ k 步
  5.  for (int i = 0; i < k; i++) {
  6.  p1 = p1.next;
  7.  }
  8.  ListNode p2 = head;
  9.  // p1 和 p2 同时⾛ n - k 步
  10.  while (p1 != null) {
  11.  p2 = p2.next;
  12.  p1 = p1.next;
  13.  }
  14.  // p2 现在指向第 n - k 个节点
  15.  return p2;
  16. }

当然，如果⽤ big O 表示法来计算时间复杂度，⽆论遍历⼀次链表和遍历两次链表的时间复杂度都是 O(N)，
但上述这个算法更有技巧性。
很多链表相关的算法题都会⽤到这个技巧，⽐如说⼒扣第 19 题「删除链表的倒数第 N 个结点」：
image.png
我们直接看解法代码：

  1. // 主函数
  2. public ListNode removeNthFromEnd(ListNode head, int n) {
  3.  // 虚拟头结点
  4.  ListNode dummy = new ListNode(-1);
  5.  dummy.next = head;
  6.  // 删除倒数第 n 个，要先找倒数第 n + 1 个节点
  7.  ListNode x = findFromEnd(dummy, n + 1);
  8.  // 删掉倒数第 n 个节点
  9.  x.next = x.next.next;
  10.  return dummy.next;
  11. }
  13. private ListNode findFromEnd(ListNode head, int k) {
  14.  // 代码⻅上⽂ }

这个逻辑就很简单了，要删除倒数第 n 个节点，就得获得倒数第 n + 1 个节点的引⽤，可以⽤我们实现的
findFromEnd 来操作。

不过注意我们⼜使⽤了虚拟头结点的技巧，也是为了防⽌出现空指针的情况，⽐如说链表总共有 5 个节点， 题⽬就让你删除倒数第 5 个节点，也就是第⼀个节点，那按照算法逻辑，应该⾸先找到倒数第 6 个节点。但 第⼀个节点前⾯已经没有节点了，这就会出错。

但有了我们虚拟节点 dummy 的存在，就避免了这个问题，能够对这种情况进⾏正确的删除。