一、二分查找法

关于二分查找法的文档见：https://blog.csdn.net/Master_cxc/article/details/91415170
二分查找防止溢出问题：https://blog.csdn.net/Jackie1377/article/details/111001491

1. 最基础二分查找

704. 二分查找 - 力扣（LeetCode）
C++版本

  1. // 版本一
  2. class Solution {
  3. public:
  4.     int search(vector<int>& nums, int target) {
  5.         int left = 0;
  6.         int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
  7.         int middle = 0;
  8.         while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
  9.             middle = left + ((right - left) >> 1);// 防止溢出 等同于(left + right)/2
  10.             if (nums[middle] > target) {
  11.                 right = middle - 1; // target 在左区间，所以[left, middle - 1]
  12.             } else if (nums[middle] < target) {
  13.                 left = middle + 1; // target 在右区间，所以[middle + 1, right]
  14.             } else { // nums[middle] == target
  15.                 return middle; // 数组中找到目标值，直接返回下标
  16.             }
  17.         }
  18.         // 未找到目标值
  19.         return -1;
  20.     }
  21. };
  24. // 版本二
  25. class Solution {
  26. public:
  27.     int search(vector<int>& nums, int target) {
  28.         int left = 0;
  29.         int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)
  30.         while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
  31.             int middle = left + ((right - left) >> 1);
  32.             if (nums[middle] > target) {
  33.                 right = middle; // target 在左区间，在[left, middle)中
  34.             } else if (nums[middle] < target) {
  35.                 left = middle + 1; // target 在右区间，在[middle + 1, right)中
  36.             } else { // nums[middle] == target
  37.                 return middle; // 数组中找到目标值，直接返回下标
  38.             }
  39.         }
  40.         // 未找到目标值
  41.         return -1;
  42.     }
  43. };

2. 搜索插入位置

35. 搜索插入位置 - 力扣（LeetCode）

image.png
image.png

（1）暴力穷举法

暴力解题不一定时间消耗就非常高，关键看实现的方式，就像是二分查找时间小号不一定就很低，是一样的。

  1. class Solution {
  2. public:
  3.     int searchInsert(vector<int>& nums, int target) {
  4.         for (int i = 0; i < nums.size(); i++) {
  5.         // 分别处理如下三种情况
  6.         // 目标值在数组所有元素之前
  7.         // 目标值等于数组中某一个元素
  8.         // 目标值插入数组中的位置
  9.             if (nums[i] >= target) { // 一旦发现大于或者等于target的num[i]，那么i就是我们要的结果
  10.                 return i;
  11.             }
  12.         }
  13.         // 目标值在数组所有元素之后的情况
  14.         return nums.size(); // 如果target是最大的，或者 nums为空，则返回nums的长度
  15.     }
  16. };
  • 时间复杂度O(n)
  • 空间复杂度O(1)

（2）二分查找法

  1. class Solution {
  2. public:
  3.     int searchInsert(vector<int>& nums, int target) {
  4.         int left = 0;
  5.         int right = nums.size() - 1;
  6.         int middle = 0;
  7.         while(left <= right){
  8.             middle = left + ((right - left) >> 2);  // 防止溢出，等价于 (left + right) / 2
  9.             if(nums[middle] > target){              // 目标值在左侧，[left, middle - 1]
  10.                 right = middle - 1;
  11.             }
  12.             else if(nums[middle] < target){         // 目标值在右侧，[middle + 1, right]
  13.                 left = middle + 1;
  14.             }
  15.             else{
  16.                 return middle;                      // 找到数组中与目标值对应的元素，返回索引
  17.             }
  18.         }
  19.         // 处理以下三种情况
  20.         // 目标值在数组所有元素之前
  21.         // 目标值在数组所有元素之后
  22.         // 目标值插入数组中某个位置
  23.         return left;                                // 或者 return right + 1; 都是可以的
  24.     }
  25. };
  • 时间复杂度O(log n)
  • 空间复杂度O(1)

解题思路：其实这道题无非是在普通的二分查找的基础上将目标值按顺序插入数组，关键在于边界的分析问题，情况可以分为四种：

  1. 数组中有与目标值相等的元素
  2. 目标值小于数组所有元素
  3. 目标值大于数组所有元素
  4. 目标值插入数组中某个位置

确定了循环不变量之后，解题思路就很清晰了。

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

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

image.png
image.png

思路

这道题目如果基础不是很好，不建议看简短的代码，简短的代码隐藏了太多逻辑，结果就是稀里糊涂把题AC了，但是没有想清楚具体细节！
寻找target在数组中的左右边界，有如下三种情况：

  1. 情况一：在数组范围内的右边或者左边，例如数组 {3, 4, 5}，target为2或者数组 {3, 4, 5}，target为6，此时应该返回 {-1, -1}
  2. 情况二：target在数组范围内，且数组中不存在target，例如数组 {3, 6, 7}，target为5，此时应该返回 {-1，-1}
  3. 情况三：target在数组范中，且数组中存在target，例如数组 {3，6，7}，target为6，此时应该返回 {1，1}

接下来，再去寻找左边界和有边界。

刚刚接触二分搜索的同学不建议上来就想如果用一个二分来查找左有边界，很容易把自己绕进去，建议扎扎实实的写两个二分分别找左边界和有边界

（1）寻找右边界

  1. // 二分查找，寻找target的右边界（不包括target）
  2. // 如果rightBorder为没有被赋值（即target在数组范围的左边，例如数组[3,3]，target为2），为了处理情况一
  3. int getRightBorder(vector<int>& nums, int target) {
  4.     int left = 0;
  5.     int right = nums.size() - 1;    // 定义target在左闭右闭的区间里，[left, right]
  6.     int rightBorder = -2;             // 记录一下rightBorder没有被赋值的情况
  7.     while (left <= right) {         // 当left==right，区间[left, right]依然有效
  8.         int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
  9.         if (nums[middle] > target) {
  10.             right = middle - 1;     // target 在左区间，所以[left, middle - 1]
  11.         } else {                     // 当nums[middle] == target的时候，更新left，这样才能得到target的右边界
  12.             left = middle + 1;
  13.             rightBorder = left;
  14.         }
  15.     }
  16.     return rightBorder;
  17. }

（2）寻找左边界

  1. // 二分查找，寻找target的左边界leftBorder（不包括target）
  2. // 如果leftBorder没有被赋值（即target在数组范围的右边，例如数组[3,3],target为4），为了处理情况一
  3. int getLeftBorder(vector<int>& nums, int target) {
  4.     int left = 0;
  5.     int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
  6.     int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况
  7.     while (left <= right) {
  8.         int middle = left + ((right - left) / 2);
  9.         if (nums[middle] >= target) { // 寻找左边界，就要在nums[middle] == target的时候更新right
  10.             right = middle - 1;
  11.             leftBorder = right;
  12.         } else {
  13.             left = middle + 1;
  14.         }
  15.     }
  16.     return leftBorder;
  17. }

（3）处理三种情况

左右边界计算完之后，看一下主题代码，这里把上面讨论的三种情况，都覆盖了

  1. // 这道题有三种情况
  2. // 1. 目标值在数组左边或者右边 eg: [3, 3] target=2 || target = 4
  3. // 2. 目标值不存在数组中
  4. // 3. 目标值在数组中，这种情况同情况一一样，都需要获取目标值的左右边界
  6. class Solution {
  7. public:
  8.     vector<int> searchRange(vector<int>& nums, int target) {
  9.         int leftBorder = getLeftBorder(nums, target);
  10.         int rightBorder = getRightBorder(nums, target);
  11.         // 情况一
  12.         if(leftBorder == -2 || rightBorder == -2){
  13.             return {-1, -1};
  14.         }
  15.         // 情况三
  16.         if(rightBorder - leftBorder > 1){
  17.             return {leftBorder + 1, rightBorder - 1};
  18.         }
  19.         // 情况二，leftBorder和rightBorder的值是不确定的
  20.         return {-1, -1};
  21.     }
  23. private:
  24.     // 获取左边界
  25.     int getLeftBorder(vector<int> nums, int target){
  26.         int left = 0;
  27.         int right = nums.size() - 1;
  28.         int leftBorder = -2;        // 初始化为-2，方便记录后续是否被赋值
  29.         while(left <= right){
  30.             int middle = left + ((right - left) >> 1);
  31.             if(nums[middle] >= target){     // 如果target落在左区间
  32.                 right = middle - 1;
  33.                 leftBorder = right;
  34.             }
  35.             else{
  36.                 left = middle + 1;
  37.             }
  38.         }
  39.         return leftBorder;
  40.     }
  42.     // 获取右边界
  43.     int getRightBorder(vector<int> nums, int target){
  44.         int left = 0;
  45.         int right = nums.size() - 1;
  46.         int rightBorder = -2;
  47.         while(left <= right){
  48.             int middle = left + ((right - left) >> 1);
  49.             if(nums[middle] <= target){     // 如果target落在右区间，我们可以找到
  50.                 left = middle + 1;
  51.                 rightBorder = left;
  52.             }
  53.             else{
  54.                 right = middle - 1;
  55.             }
  56.         }
  57.         return rightBorder;
  58.     }
  59. };

这份代码在简洁性很有大的优化空间，例如把寻找左右区间函数合并一起。
但拆开更清晰一些，而且把三种情况以及对应的处理逻辑完整的展现出来了。

（4）我的解题感想：

  1. 首先，这道题的难点一是：你很难去想到去寻找目标值在数组的左右边界，而且这个边界是目标值的前一位和后一位，这是难点之一。
  2. 第二个难点是：二分查找一般是找到目标值我们就退出循环，但这里明显要继续去找其他的索引，怎么解决这个问题，这是难点二。
  3. 难点三就是对二分查找的理解，二分查找的最高消耗就是当 left <= right 的循环条件被打破，这时 right + 1 = left，而在此之前，left、right、middle指向同一个索引，因此要找到目标值的右边界，只需将 rightBorder = left 即 rightBorder = middle + 1，同理，左边界 leftBorder = right 即 leftBorder = middle - 1，这很好的解释了上面代码的思想。

4. sqrt(x)

69. x 的平方根 - 力扣（LeetCode）

思路：

使用整数的排序属性来减少搜索空间。
自然数就是一个公差为 1 的等差数列。由于题目只要求整数部分，所以只需要找到 某个数 n 的平方大于 x 且 n - 1 的平方小于 x ，那么 n - 1 这个数就是我们要的。即使用二分查找，有两种情况需要分析：

  1. 数组刚好有一个目标值，target^2 == x;
  2. 数组中没有对应的目标值，根据二分查找的特点，最后 left == right == middle，最后一个判定条件：
  • 如果 middle^2 > x，leftBorder == right == middle - 1；leftBorder 等于 middle的前一位。
  • 如果 middle^2 < x，left = middle + 1；这个时候 leftBorder 还是等于right；leftBorder 等于 middle。

代码：

  1. class Solution {
  2. public:
  3.     int mySqrt(int x) {
  4.         int leftBorder = getLeftBorder(x);
  5.         if(leftBorder == 0){
  6.             return 0;
  7.         }
  8.         else{
  9.             return leftBorder;
  10.         }
  11.     }
  13. private:
  14.     // 获取左边界
  15.     int getLeftBorder(int x){
  16.         // x 等于 0 需要做一个单独的判断，不然 left得从0开始，这样会造成下面middle为0的问题
  17.         if(x == 0){
  18.             return 0;
  19.         }
  20.         else{
  21.             int leftBorder = -2;
  22.             int left = 1;
  23.             int right = x;
  24.             int middle = -1;
  25.             while(left <= right){
  26.                 middle = left + ((right - left) >> 1);  // 防止溢出，等价于 (left + right) / 2
  27.                 if(middle > x / middle){    // 防止溢出，等价于 middle * middle > x
  28.                     right = middle - 1;
  29.                     leftBorder = right;     // 获取左边界，leftBorder永远在 middle^2 > x 的 middle左边
  30.                 }
  31.                 else if(middle == x / middle){
  32.                     return middle;
  33.                 }
  34.                 else{
  35.                     left = middle + 1;
  36.                 }
  37.             }
  38.             return leftBorder;
  39.         }
  40.     }
  41. };

（1）我的解题感想：

这道题有两个难点：

  1. 要想到利用 一个有序的数组，然后通过二分查找目标值有点小难度。
  2. 需要对二分查找的边界条件的理解比较清晰，当数组中没有目标值，循环最后一次条件肯定是 left == right，这个时候无论走的是哪个判定条件，leftBorder 总是能够满足题解。即 x 的算数平方根的整数部分。

5. 有效的完全平方数

367. 有效的完全平方数 - 力扣（LeetCode）

  1. class Solution {
  2.     public:
  3.     bool isPerfectSquare(int num) {
  4.         int L = 1, R = num;
  5.         int M = 0;
  6.         while(L <= R){
  7.             M = L + ((R - L) >> 1);
  8.             long square =(long) M * M;    // 强制类型转换
  9.             if(square > num){
  10.                 R = M - 1;
  11.             }
  12.             else if(square < num){
  13.                 L = M + 1;
  14.             }
  15.             else{
  16.                 return true;
  17.             }
  18.         }
  19.         return false;
  20.     }
  21. };

这道题简单，不写题解。

6. 平方数之和

力扣第 633 题：https://leetcode-cn.com/problems/sum-of-square-numbers/

二、移除元素

1. 移除元素

力扣第 27 题：https://leetcode-cn.com/problems/remove-element/submissions/

双指针法
双指针法（快慢指针法）：通过一个块指针和一个慢指针在一个for循环下完成两个for循环的工作。

  • 快指针：指向当前要处理的元素
  • 指向下一个将要赋值的位置

思路：

  • 如果快指针指向的元素不等于val，它一定是输出数组的一个元素，我们就将快指针指向的元素赋值到慢指针位置，然后将快慢指针同时右移。
  • 如果快指针指向的元素等于val，它不能输出在数组里，此时慢指针不动，快指针右移一位。

整个过程保持不变的性质是：区间 [0，left) 中的元素都不等于val。当左右指针遍历完输入数组以后，left的值就是输出数组的长度。

  1. // 时间复杂度：O(n)
  2. // 空间复杂度：O(1)
  3. class Solution{
  4. public:
  5.     int removeElement(vector<int>& nums, int val){
  6.         int slowIndex = 0;
  7.         for(int fastIndex = 0; fastIndex < nums.size(); fastIndex++){
  8.             if(nums[fastIndex] != val){
  9.                 nums[slowIndex] = nums[fastIndedx];
  10.                 slowIndex++;
  11.             }
  12.         }
  13.         return slowIndex;
  14.     }
  15. }

2. 删除有序数组中的重复项

力扣第 26 题：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

思路：
利用双指针法，快指针指向当前要处理的元素，慢指针指向下一个将要赋值的位置。
题目给的是有序数组，这个时候很容易联想到二分查找法，但是这里很明显是要将数组遍历一遍，所以我没有想出时间复杂度小于O(n)的解法，事实也确实没有。
需要注意的是数组的边界问题。

  1. class Solution {
  2. public:
  3.     int removeDuplicates(vector<int>& nums) {
  4.         if(nums.size() <= 1) return nums.size();
  5.         int slowIndex = 0;      // 慢指针
  6.         for(int fastIndex = 0; fastIndex < nums.size(); fastIndex++){
  7.             if(fastIndex >= 1 && nums[fastIndex] == nums[fastIndex - 1]){
  8.                 continue;
  9.             }
  10.             nums[slowIndex] = nums[fastIndex];
  11.             slowIndex++;
  12.         }
  13.         return slowIndex;
  14.     }
  15. };

3. 移动零

力扣第 283 题：https://leetcode-cn.com/problems/move-zeroes/

还是双指针法，太简单了，需要注意的是题目已经给出了目标值0，所以直接覆盖就行了，没必要进行跟其他元素进行交换，这样虽然复杂度一样，但会增加很多多余的操作。

  1. class Solution {
  2. public:
  3.     // 时间复杂度O(n)
  4.     // 空间复杂度O(1)
  5.     void moveZeroes(vector<int>& nums) {
  6.         int left = 0;   // left的左边都是非0整数
  7.         for(int right = 0; right < nums.size(); right++){
  8.             if(nums[right] != 0){
  9.                 nums[left++] = nums[right];     // left的长度就是非零整数的长度
  10.             }
  11.         }
  12.         for(int i = left; i < nums.size(); i++){
  13.             nums[i] = 0;
  14.         }
  15.     }
  16. };

4. 比较含退格的字符串

力扣第 844 题：https://leetcode-cn.com/problems/backspace-string-compare/submissions/
这道题我没有解出来

思路：
这道题用栈的思路就很简单，难点是使用双指针，链接是题解：https://leetcode-cn.com/problems/backspace-string-compare/solution/shuang-zhi-zhen-bi-jiao-han-tui-ge-de-zi-8fn8/，但是二者的复杂度是一样的，所以还是使用栈比较好。

  1. class Solution{
  2. public:
  3.     // 时间复杂度O(n+m)
  4.     // 空间复杂度O(1)
  5.     bool backspaceCompare(string s, string t) {
  6.         return backSpace(s) == backSpace(t);
  7.     }
  9.     string backSpace(string str) {
  10.         string stack;
  11.         for(char ch: str) {
  12.             if(ch != '#') { 
  13.                stack.push_back(ch);        // 如果 ch != '#' 就入栈
  14.             }
  15.             else{
  16.                 stack.pop_back();        // 如果 ch == '#' 就出栈
  17.             }
  18.         }
  19.         return stack;
  20.     }
  21. }

三、有序数组

1. 有序数组的平方

977. 有序数组的平方 - 力扣（LeetCode）
image.png

思路
数组其实是有序的，只不过负数平方之后可能变成最大的数，那么数组元素平方之后的最大值不是在左边就是在右边（这是必须要想到的点），不可能在左边，这样的话，我们只需要通过比较数组左右两边平方后的元素大小，就可以得到一个有序的数组。此时就可以使用双指针法了。left指向起始位置，right指向终止位置。
但是需要new一个新数组result来保存这个有序的数列（空间换时间），让end指向result的末尾。

  • 如果nums[left] * nums[left] > nums[right] * nums[right] ，那么 result[end--] = nums[left] * nums[left]，left++；
  • 如果nums[left] * nums[left] <= nums[right] * nums[right]，那么result[end--] = nums[right] * nums[right]，right—；

by the way，这道题我没有做出来，操！

  1. class Solution{
  2. public:
  3.     vector<int> sortedSquares(vector<int>& nums){
  4.         int length = nums.size();
  5.         int end = length - 1;                    // 指向result的末尾
  6.         vector<int> result(length, 0);            // 声明一个vector容器变量，并将各个元素初始化为0
  7.         for(int left = 0, right = length - 1; left <= right;){        // 这里<=，是因为最后面要处理两个数
  8.             if(nums[left] * nums[left] > nums[right] * nums[right]){
  9.                 result[end--] = nums[left] * nums[left];
  10.                 left++;            // 往前移动一个位置
  11.             }
  12.             else{
  13.                 result[end--] = nums[right] * nums[right];
  14.                 right--;        // 往后移动一个位置
  15.             }
  16.         }
  17.         return result;            // 返回result数组
  18.     }
  19. }

2. 合并两个有序数组

力扣第 88 题：https://leetcode-cn.com/problems/merge-sorted-array/

  1. class Solution {
  2. public:
  3. // 数组 nums1 和 nums2 原本就是有序（升序）的，所以最大值要么在 num1的右侧，要么在num2的右侧
  4. // 因此可以使用双指针法
  5.     void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
  6.         int p1 = m - 1;         // 指向数组nums1元素值不为0的尾部
  7.         int p2 = n - 1;         // 指向数组nums2的尾部
  8.         int tail = m + n - 1;   // 指向数组nums1的尾部
  9.         int cur = 0;
  10.         while(p1 >= 0 || p2 >= 0){      // 这里用或很重要，意味着p1 || p2 可以不同时小于零（这是我没有想到的）
  11.             if(p1 == -1){
  12.                 cur = nums2[p2--];
  13.             }
  14.             else if(p2 == -1){
  15.                 cur = nums1[p1--];
  16.             }
  17.             else if(nums1[p1] > nums2[p2]){
  18.                 cur = nums1[p1--];
  19.             }
  20.             else{
  21.                 cur = nums2[p2--];
  22.             }
  23.             nums1[tail--] = cur;
  24.         }
  25.     }
  26. };

3. 区间列表的交集

力扣第 986 题：https://leetcode-cn.com/problems/interval-list-intersections/

复杂度分析：

  • 时间复杂度：O(M + N)，其中M，N分别是数组firstList和数组secondList的长度。
  • 空间复杂度：O(M + N)，答案中区间数量的上限。
    1. class Solution {
    2. public:
    3.   vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {
    4.       // 双指针法
    5.       int i = 0;      // 指针i，指向firstList数组
    6.       int j = 0;      // 指针j，指向secondList数组
    7.       vector<vector<int>> result;     // 结果数组，用来存放交集区间
    8.       while(i < firstList.size() && j < secondList.size()){
    9.           // left是result数组区间列表的左区间，right是result数组区间的右区间
    10.           // 需要先判断left来自哪个数组，同时也需要先判断right来自哪个数组
    11.           // 方便后续是对i++，还是对j++
    12.           int left = max(firstList[i][0], secondList[j][0]);
    13.           int right = min(firstList[i][1], secondList[j][1]);
    14.           // 只有left在right的左侧(或重叠)的时候才是交集
    15.           if(left <= right){
    16.               result.push_back({left, right});
    17.           }
    18.           // 如果firstList[i][1]比secondList[i][1]大，那么需要对firstList[i][1]进行下一步判断，
    19.           // 判断其是否跟secondList的下一个区间列表相交了
    20.           if(firstList[i][1] > secondList[j][1]){
    21.               j++;
    22.           }
    23.           else{
    24.               i++;
    25.           }
    26.       }
    27.       return result;
    28.   }
    29. };

这道题的难点在于：下面这种情况
image.png
当 firstList的尾部比secondList的尾部大的时候，是需要对firstList[i][1]保留然后进行下一步判断的，判断其是否大于secondList的下一个区间列表的头部，如果大于说明跟secondList的下一个区间列表相交了，这样的话需要一直重复上面的操作。

四、滑动窗口

1. 长度最小的子数组

力扣第 209 题：https://leetcode-cn.com/problems/minimum-size-subarray-sum/

（1）暴力解法：

  • 时间复杂度：O(n^2)
  • 空间复杂度：O(1)
    1. class Solution {
    2. public:
    3.   int minSubArrayLen(int target, vector<int>& nums) {
    4.       int sum = 0;
    5.       int length = INT_MAX;
    6.       for(int i = 0; i < nums.size(); i++){
    7.           sum = 0;
    8.           for(int j = i; j < nums.size(); j++){
    9.               if(nums[j] < target){
    10.                   sum = sum + nums[j];
    11.               }
    12.               if(nums[j] >= target){
    13.                   return 1;
    14.               }
    15.               if(sum >= target){
    16.                   if(length > j - i + 1){
    17.                       length =  j - i;           // 长度最小的连续子数组的长度保存在length中
    18.                       break;                     // 退出当前for循环
    19.                   }
    20.               }
    21.           }
    22.       }
    23.       if(length == INT_MAX){
    24.           return 0;
    25.       }
    26.       else{
    27.           return length;
    28.       }
    29.   }
    30. };

（2）前缀 + 二分查找

  1. class Solution {
  2. public:
  3.     int minSubArrayLen(int s, vector<int>& nums) {
  4.         int n = nums.size();
  5.         if (n == 0) {
  6.             return 0;
  7.         }
  8.         int ans = INT_MAX;
  9.         vector<int> sums(n + 1, 0); 
  10.         // 为了方便计算，令 size = n + 1 
  11.         // sums[0] = 0 意味着前 0 个元素的前缀和为 0
  12.         // sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
  13.         // 以此类推
  14.         for (int i = 1; i <= n; i++) {
  15.             sums[i] = sums[i - 1] + nums[i - 1];
  16.         }
  17.         for (int i = 1; i <= n; i++) {
  18.             int target = s + sums[i - 1];
  19.             auto bound = lower_bound(sums.begin(), sums.end(), target);
  20.             if (bound != sums.end()) {
  21.                 ans = min(ans, static_cast<int>((bound - sums.begin()) - (i - 1)));
  22.             }
  23.         }
  24.         return ans == INT_MAX ? 0 : ans;
  25.     }
  26. };

难点：

  1. 因为数组元素非负，所以可以利用累加求和的方式让数组变成一个有序数组。这一点比较难想到。
  2. 对目标元素不变量的确定，即 target = s + sums[i - 1]。其实每一次循环都去找大于目标值的连续子数组，然后对找到的子数组的长度进行迭代。第 i 次寻找的时候，由于数组的前 i 项元素的和，所以需要减去前 i - 1 项的和，但这时候我们令 s + sums[i - 1]，这样就不必执行 sums[i] - sums[i - 1]这样难以实现操作的。我觉得这是难点2.
  3. 为什么sums数组的长度要确定为 n + 1？
    • 原因：因为当遍历完数组nums后，这个时候 i 指向的是最后一个元素，那么这个时候如何判断是否大于或等于target呢？这个时候如果多开一个位置就可以将 nums的最后一个元素也进行统一判断了。即如果 i 指向了 sums.end()，这个数组就不满足条件。

（3）滑动窗口

  1. class Solution {
  2. public:
  3.     int minSubArrayLen(int target, vector<int>& nums){
  4.         int n = nums.size();
  5.         int i = 0;        // 滑动窗口的其实地址
  6.         int sum = 0;    // 滑动窗口的和
  7.         int subLength = 0;    // 滑动窗口的长度
  8.         int result = INT_MAX;    // 结果长度，初始化为最大
  9.         for(int j = 0; j < n; j++){
  10.             if(nums[j] >= target){        // 如果存在一个元素大于或等于target，则直接返回1；
  11.                 return 1;
  12.             }
  13.             sum = sum + nums[j];
  14.             while(sum >= target){
  15.                 subLength = j - i + 1;
  16.                 result = result < subLength ? result : subLength;
  17.                 sum = sum - nums[i++];    // 滑动窗口的精髓，不断变更i（子数组的其实位置）
  18.             }
  19.         }
  20.     }
  21. }

2. 最长重复子数组

力扣第 718 题：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/

解法：滑动窗口
思路及算法
我们注意到之所以两位置会比较多次，是因为重复的子数组在两个数组中的位置可能不同。以 A = [3，6，1，2，4]，B = [7，1，2，9]为例，我们最长重复子数组是 [1，2]，在A与B中的开始位置不同。但如果我们知道了开始位置，我们就可以根据它们将 A 和 B 进行 [ 对齐 ]，即：

  1. A = [3, 6, 1, 2, 4]
  2. B =    [7, 1, 2, 9]
  3.            ↑  ↑
  4. --------------------------------
  5. // 我们可以枚举 A 和 B 的所有对齐方式。对齐的方式有以下两类
  6. A = [0, 1 ,2, 3, 4, 0, 0]  --> A固定,B滑动  A = [0, 1, 2, 3, 4, 0, 0]
  7. B = [1, 2, 3, 4, 1, 1, 1]                   B =    [1, 2, 3, 4, 1, 1, 1]     
  8.                                                     ↑
  10. A = [0, 1 ,2, 3, 4, 0, 0]                    A =    [1, 2, 3, 4, 1, 1, 1]
  11. B = [1, 2, 3, 4, 1, 1, 1]  --> B固定,A滑动  B = [0, 1, 2, 3, 4, 0, 0]     
  12.                                                     ↑

c++代码实现：
复杂度分析

  • 时间复杂度： O((N + M) * min(N, M))

  • 空间复杂度： O(1)

    1. class Solution{
    2. public:
    3.   int maxLength(vector<int>& A, vector<int>& B, int addA, int addB, int len){
    4.       int result = 0;
    5.       int k = 0;
    6.       for(int i = 0; i < len; i++){
    7.           if(A[addA + i] == B[addB + i]){
    8.               k++;
    9.           }
    10.           else{
    11.               k = 0;
    12.           }
    13.           result = max(result, k);
    14.       }
    15.       return result;
    16.   }
    18.   int findLength(vector<int>& nums1, vector<int>& nums2){
    19.       int n1 = nums1.size();
    20.       int n2 = nums2.size();
    21.       int len = 0;
    22.       int subLength = 0;            // 滑动窗口的长度
    23.       int result = 0;                // 最终结果
    24.       // A固定，B相对A向右滑动
    25.       for(int i = 0; i < n1; i++){
    26.           len = min(n1 - i, n2);    // 防止数组越界，同时n1 - i，是nums2与nums1对齐后需要判断的长度
    27.           subLength = maxLength(nums1, nums2, i, 0, len);
    28.           result = max(result, subLength);
    29.       }
    30.       // B固定，A相对B向右滑动
    31.       for(int i = 0; i < n2, i++){
    32.           len = min(n1, n2 - i);
    33.           subLength = maxLength(nums1, nums2, 0, i, len);
    34.           result = max(result, subLength);
    35.       }
    36.       return result;
    37.   }
    38. }

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

力扣第 3 题：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
思路与算法
因为要寻找字符串 s = “abcabcdd” 的无重复字符的最长子串，所以肯定至少要遍历一遍 s 才能遍历所有可能性，通常来说，找子数组或者子串这类问题，首先想到的就是用双指针来解决。这道题看题来更像滑动窗口，所以可以用滑动窗口的思想来解决。。

  • 我们使用指针 i 和指针 right 分别指向枚举子串的起始位置和滑动窗口向右滑动的滑动指针。
  • 在每一步操作中，将左指针向右移动一格，表示我们枚举下一个字符作为起始位置，然后我们可以不断地向右移动右指针，但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后，这个子串就对应着以左指针开始的，不包含重复字符的最长子串。我们记录下这个子串的长度。
  • 在枚举结束后，我们找到的最长的子串的长度即为答案。

判断重复字符
在上面的流程中，我们还需要使用一种数据结构来判断是否有重复的字符，常用的数据结构为哈希集合（即C++中的 std::unordered_set，Java 中的 HashSet，Python 中的 set，JavaScript 中的 Set ）。在左指针向右移动的时候，我们从哈希集合中移除一个字符，在右指针向右移动的时候，我们往哈希集合添加一个字符。

C++代码：

  • 时间复杂度O(n)
  • 空间复杂度O(m),m是子串的长度，最长为数组的长度n
    1. class Solution {
    2. public:
    3.   int lengthOfLongestSubstring(string s) {
    4.       unordered_set<char> occ;    // 声明一个哈希集合的变量
    5.       int right = -1;          // 滑动指针,从数组第一个位置的左侧开始，这样子right+1才能遍历到所有的元素
    6.       int ans = 0;
    7.       for(int i = 0; i < s.length(); ++i){    // 需要遍历一遍字符串，才能找到最长子串
    8.           if(i != 0){
    9.               occ.erase(s[i - 1]);
    10.           }
    11.           while(right + 1 < s.length() && !occ.count(s[right + 1])){   // !occ.count(s[right+1]) 保证我们得到的是一个无重复子串
    12.               occ.insert(s[right + 1]);
    13.               right++;        // 向右滑动
    14.           }
    15.           ans = max(ans, right - i + 1);
    16.       }
    17.       return ans;
    18.   }
    19. };

4. 水果成篮

力扣第 904 题：https://leetcode-cn.com/problems/fruit-into-baskets/

我的代码：
时间复杂度O(n2)

  1. class Solution {
  2. public:
  3.     int totalFruit(vector<int>& fruits) {
  4.         unordered_set<int> hashset;
  5.         int type = 0;       // 水果类型
  6.         int right = 0;      // 子串右指针
  7.         int subLength = 0;  // 当前窗口的长度
  8.         for(int i = 0; i < fruits.size(); i++){
  9.             right = i;          // 右指针从子串的起始位置开始滑动
  10.             type = 0;           // 水果类型重置为0
  11.             if(i == right){     // 如果是子串的起始位置，那么第1棵数肯定能被采摘
  12.                 hashset.insert(fruits[i]);
  13.                 type++;     // 水果类型加1
  14.                 subLength = max(subLength, right - i + 1);
  15.             }
  16.             while(type <= 2 && right + 1 < fruits.size()){    // 用right+1是为了防止越界
  17.                 if(hashset.count(fruits[right + 1])){       // 如果 fruits[right + 1]在前面出现过了，表明是同一棵树，type不用+1
  18.                     hashset.insert(fruits[right + 1]);
  19.                     right++;
  20.                     subLength = max(subLength, right - i + 1);
  21.                 }
  22.                 else{
  23.                     hashset.insert(fruits[right + 1]);
  24.                     right++;
  25.                     type++;
  26.                     if(type <= 2){      // 只有类型不大于2的子串的长度才是我们想要的
  27.                         subLength = max(subLength, right - i + 1);
  28.                     }
  29.                 }
  30.             }
  31.             hashset.clear();    // 将之前的存入的数全部丢弃
  32.         }
  33.         return subLength;
  34.     }
  35. };

题解：
这道题最关键的问题是：解题人能不能想到用哈希表来解这道题。
我的理解：
因为只有两个篮子，说白了就是找到由两个数值组成的最长且连续的子串，所以就可以通过哈希映射来存储这些键值对（键是fruits的元素，值是这个元素出现的次数）。我们只需要记录某个元素出现的次数，这个特性与哈希映射键值对的特征符合。
接着我们只需要判断哈希映射的size是否大于2即可，如果大于2，我们就让最前面的元素出现的次数减1，然后长度跟着减1，知道这个元素出现的次数为0，那么我们删除这个元素。在整个过程中，我们都要不断迭代子串的长度。

  1. class Solution{
  2. public:
  3.     // 时间复杂度O(n),其中n是fruits的长度
  4.     // 空间复杂度O(n)
  5.     int totalFruit(vector<int>& fruits){
  6.         unordered_map<int, int> map;
  7.         int len = 0;                            // 当前子串长度
  8.         int result = 0;                            // 结果
  9.         int right = 0;                            // 滑动指针
  10.         for(int i = 0; i < fruits.size(); i++){
  11.             map[fruits[i]]++;                    // 第i个元素出现的次数
  12.             len++;                                // 长度+1
  13.             while(map.size() > 2){                // 如果哈希表的长度大于2
  14.                 map[fruits[right]]--;            // 最前面的元素出现的次数减1
  15.                 if(map[fruits[right]] == 0){
  16.                     map.erase(fruits[right]);
  17.                 }
  18.                 right++;                        // right的值就是元素的索引
  19.                 len++;
  20.             }
  21.             result = result > len ? result : len;
  22.         }
  23.         return result;
  24.     }
  25. }

5. 最小覆盖子串

76. 最小覆盖子串 - 力扣（LeetCode）

思路和算法
本问题要求我们返回字符串s中包含字符串t的全部字符的最小窗口。我们成包含t的全部字母的窗口为可行窗口。
我们可以用滑动窗口的思想解决这个问题。在滑动窗口类型的问题中都会有两个指针，一个用于【延伸】现有窗口的 right 指针，和一个用于【收缩】窗口的 left 指针。在任意时刻，只有一个指针运动，而另一个保持静止。我们在 s 上滑动窗口，通过移动 r 指针不断扩张窗口。当窗口包含 t 全部所需的字符后，如果能收缩，我们就收缩窗口直到得到最小窗口。

这道题最关键的一步我觉得是，你要想到去利用 t 中的字符，即通过 t_map[t[right]] 来判断 s 当前的字符是不是有用的字符，这一点十分关键。

  1. class Solution{
  2. public:
  3.     unordered_map<char, int> t_map, s_map;
  5.     // check函数，用来检查s_map是否涵盖了t_map中的所有字符，且s_map中的字符出现的次数不少于t_map中的
  6.     bool check(){
  7.         for(const auto &p : t_map){
  8.             if(s_map[p.first] < p.second){
  9.                 return false;
  10.             }
  11.         }
  12.         return true;
  13.     }
  15.     string minWindow(string s, string t){
  16.         for(const auto &c : t){        // 将t中的字符存入到t_map中
  17.             t_map[c]++;
  18.         }
  19.         int left = 0;                // 收缩指针
  20.         int right = -1;                // 扩张指针
  21.         int len = INT_MAX;            // 窗口长度
  22.         int minL = -1;                // 指针收缩到窗口长度最小时候的位置
  23.         while(right < int(s.size())){
  24.             if(t_map.find(s[++right]) != t_map.end()){
  25.                 s_map[s[right]]++;
  26.             }
  27.             while(check() && left <= right){
  28.                 if(len > right - left + 1){        // 更新窗口长度
  29.                     len = right - left + 1;
  30.                     minL = left;
  31.                 }
  32.                 if(t_map.find(s[left]) != t_map.end()){        // 窗口满足收缩的条件
  33.                     s_map[s[left]]--;            // 把最开始出现的字符跳过，寻找下一个窗口
  34.                 }
  35.                 left++;                            // 收缩窗口
  36.             }
  37.         }
  38.         return minL == -1 ? string() : s.substr(minL, len);
  39.     }
  40. };

复杂度分析：

  • 时间复杂度：最坏情况下左右指针对 ss 的每个元素各遍历一遍，哈希表中对 ss 中的每个元素各插入、删除一次，对 tt 中的元素各插入一次。每次检查是否可行会遍历整个 tt 的哈希表，哈希表的大小与字符集的大小有关，设字符集大小为 CC，则渐进时间复杂度为 O(C⋅∣s∣+∣t∣)。
  • 空间复杂度：这里用了两张哈希表作为辅助空间，每张哈希表最多不会存放超过字符集大小的键值对，我们设字符集大小为 CC ，则渐进空间复杂度为 O(C)O(C)。

五、模拟行为

1. 螺旋矩阵II

59. 螺旋矩阵II - 力扣（LeetCode）

思路：
本题并不涉及到什么算法，就是模拟过程，但却十分考察对代码的掌控能力。
要如何画出这个螺旋排列的正方形矩阵呢？这是一个关键问题。

  1. 关键1：题目给我们一个正整数n，首先我们需要知道如何去画这个螺旋矩阵。第一，要明确的知道这个螺旋矩阵旋转的圈数。我们需要找出这个规律。（比如当n=5时，螺旋矩阵循环的次数为 5 / 2 = 2次）
  2. 关键2：坚持循环不变量原则（这里使用左闭右开原则）。

模拟顺时针画矩阵的过程

  • 填充上行从左到右
  • 填充右列从上到下
  • 填充下行从右到左
  • 填充左列从下到上

由外向内一圈一圈画下去。
image.png

  1. 关键3：需要对特殊情况进行处理。例如：当n为奇数时，需要对最后一个元素n2进行特殊处理。这最后一个元素的位置是螺旋矩阵的中心坐标。

    1. class Solution{
    2. public:
    3.  vector<vector<int>> generateMatrix(int n){
    4.      vector<vector<int>> Array2D(n, vector<int>(n, 0));    // 定义一个二维数组,并将其元素初始化为0
    5.      int circle = n / 2;            // 循环的次数,例如n=3，螺旋矩阵循环的次数为1，n=5时,螺旋矩阵循环的次数为2
    6.      int x_start = 0, y_start = 0;        // 每次循环都重新设置螺旋矩阵的起始坐标
    7.      int mid = n / 2;                    // 中心坐标，只有n为奇数时，中心坐标才会被拿来使用
    8.      int count = 1;                        // 计数器，计1-n2中间的数，并将每个数赋给Array2D中的每个位置
    9.      int offset = 1;                        // 每一圈循环都需要控制每条边的长度，因为n是长度，而数组下表从0开始，所以offset初始化为1
    10.      int x, y;
    11.      while(circle > 0){            // 螺旋矩阵旋转的次数
    12.          x = x_start;
    13.          y = y_start;
    15.          // 下面4个for循环就是模拟旋转一圈
    16.          // 顶部，自左向右
    17.          for(; x < x_start + n - offset; x++){
    18.              Array2D[y][x] = count++;
    19.          }
    20.          // 右侧，自上向下
    21.          for(; y < y_start + n - offset; y++){
    22.              Array2D[y][x] = count++;
    23.          }
    24.          // 底部，自右向左
    25.          for(; x > x_start; x--){
    26.              Array2D[y][x] = count++;
    27.          }
    28.          // 左侧，自下向上
    29.          for(; y > y_start; y--){
    30.              Array2D[y][x] = count++;
    31.          }
    33.          circle--;        // 循环次数减1
    34.          x_start++;        // 重新设计起始坐标，每循环一圈，起始坐标x和y都+1
    35.          y_start++;
    36.          offset += 2;    // 经过一圈循环后，offset的值要加2
    37.      }
    38.      // 如果n是奇数,需要对最后一个元素进行特殊处理
    39.      if(n % 2 == 1){
    40.          Array2D[mid][mid] = count;
    41.      }
    43.      return Array2D;
    44.  }
    45. };

2. 螺旋矩阵

54. 螺旋矩阵 - 力扣（LeetCode）

思路：
没什么好讲的，会上面的螺旋矩阵II，这一道题也会了（一样的思想，变通一下就行了）。主要是找规律，对不在循环内的边界数字进行额外的判断。在注释中我也说的很明白了。

  1. class Solution {
  2. public:
  3.     vector<int> spiralOrder(vector<vector<int>>& matrix) {
  4.         int m = matrix.size();          // 获得二维数组的行数
  5.         int n = matrix[0].size();       // 获得二维数组的列数
  6.         vector<int> array(m * n, 0);    // 定义一个数组
  7.         int circle = min(m, n) / 2;     // 螺旋矩阵旋转的圈数
  8.         int x_start = 0;                // 螺旋矩阵每一圈的起始位置
  9.         int y_start = 0;
  10.         int x, y;
  11.         int count = 0;                  // array数组当前位置的索引
  12.         int offset = 1;                 // 每一次循环都需要控制每次访问的窗口的长度
  13.         int specialNum = max(m, n) - 2 * ((min(m, n) / 2));
  14.         // 如果n != m且min(m,n)为奇数，则是一个矩阵，且需要对最后 max(m,n) - 2*((min(m,n)/2)) 个元素进行特殊处理
  15.         // 如果n = m且都为奇数，则只需要最后一个元素进行特殊处理
  16.         while(circle > 0){
  17.             x = x_start;
  18.             y = y_start;
  19.             // 下面4个for循环表示一圈(循环不变量是每个for循环的窗口都是左闭右开区间)
  20.             // 顶部,从左到右
  21.             for(; x < x_start + n - offset; x++){
  22.                 array[count++] = matrix[y][x];
  23.             }
  24.             // 右侧,从上到下
  25.             for(; y < y_start + m - offset; y++){
  26.                 array[count++] = matrix[y][x];
  27.             }
  28.             // 底部,从右到左
  29.             for(; x > x_start; x--){
  30.                 array[count++] = matrix[y][x];
  31.             }
  32.             // 左侧,从下到上
  33.             for(; y > y_start; y--){
  34.                 array[count++] = matrix[y][x];
  35.             }
  36.             x_start++;      // 每经过一圈，起始坐标都往右下角移动一个单元
  37.             y_start++;
  38.             offset += 2;    // offset需要+2
  39.             circle--;
  40.         }
  41.         // 如果m=n=奇数，只需要对最后一个元素进行处理
  42.         if(m == n && n % 2 == 1){
  43.             array[count++] = matrix[y_start][x_start];
  44.         }
  45.         else if(n != m && min(m, n) % 2 == 1){
  46.             if(n == min(m, n)){                 // 如果最小值是n，那么最后需要处理的元素的坐标是垂直向下走的
  47.                 while(specialNum > 0){          // 需要特殊处理的数量
  48.                     array[count++] = matrix[y_start][x_start];
  49.                     y_start++;
  50.                     specialNum--;
  51.                 }
  52.             }
  53.             else if(m == min(m, n)){
  54.                 while(specialNum > 0){          // 如果最小值是m，那么最后需要处理的元素的坐标是水平向右走的
  55.                     array[count++] = matrix[y_start][x_start];
  56.                     x_start++;
  57.                     specialNum--;
  58.                 }
  59.             }
  60.         }
  61.         return array;
  62.     }
  63. };

六、总结

数组是存放在连续内存空间的相同类型数据的集合。
数组可以方便的通过下标索引的方式获取下标对应的数据。需要注意的两点：

  • 数组下标都是从0开始的
  • 数组内存空间的地址是连续的

正因为数组的内存空间的地址是连续的，所以我们在删除或者添加一个元素的时候，就难免要移动其他元素的地址。
数组的元素是不能删除的，只能覆盖。
那么二维数组 int [3][4] 在内存中的空间地址是连续的吗？二维数组在内存中不是 3 * 4 的连续地址空间，而是 3 条连续的地址空间组成。

二分法 —> 双指针 —> 滑动窗口 —> 模拟行为

更详细的总结见：数组基础总结（代码随想录）