数组是存放在连续内存空间上的相同类型数据的集合。
下标从0开始
空间是连续的
元素不可删除只能覆盖

1.二分查找法

前提：数组有序，且不重复（重复会返回多个下标）
保证区间定义清晰，坚持循环不变量原则
左闭右闭写法：

  • while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
  • if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1

示例：

  1.         int left = 0;
  2.         int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
  3.         while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
  4.             int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
  5.             if (nums[middle] > target) {
  6.                 right = middle - 1; // target 在左区间，所以[left, middle - 1]
  7.             } else if (nums[middle] < target) {
  8.                 left = middle + 1; // target 在右区间，所以[middle + 1, right]
  9.             } else { // nums[middle] == target
  10.                 return middle; // 数组中找到目标值，直接返回下标
  11.             }
  12.         }
  13.         // 未找到目标值
  14.         return -1;

左闭右开写法：

  • while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的
  • if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]

示例：

  1. int left = 0;
  2.         int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)
  3.         while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
  4.             int middle = left + ((right - left) >> 1);
  5.             if (nums[middle] > target) {
  6.                 right = middle; // target 在左区间，在[left, middle)中
  7.             } else if (nums[middle] < target) {
  8.                 left = middle + 1; // target 在右区间，在[middle + 1, right)中
  9.             } else { // nums[middle] == target
  10.                 return middle; // 数组中找到目标值，直接返回下标
  11.             }
  12.         }
  13.         // 未找到目标值
  14.         return -1;

相关题目：

35. 搜索插入位置

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

69. x 的平方根

平方根解法可以用二分法夹逼出数组的运用 - 图1(直到a和b相差为1）

367. 有效的完全平方数

此题可以参考69的解法，当数组的运用 - 图2时即为解

我的解答：https://github.com/kaixuhuang/CPP/blob/master/array/erfen.cpp

2.移除元素

要点：不能移除数组中单个元素，只能覆盖

相关题目：

27. 移除元素

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

此题需要原地修改，因此当不重复时对慢指针进行+1，返回前n个不重复的值

283. 移动零

此题也是原地修改，方法同26，修改前n个位置为不重复的元素，在后面补充0

977. 有序数组的平方

由于是有序数组，可以从两端求平方，将较小的值存进新数组里
我的解答：https://github.com/kaixuhuang/CPP/blob/master/array/yichu.cpp

3.滑动窗口

所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
多用于求子数组
主要确定如下三点：

  • 窗口内是什么？
  • 如何移动窗口的起始位置？
  • 如何移动窗口的结束位置？

滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。

相关题目：

904. 水果成篮

采用滑动窗口，设立两个果篮，当超出果篮时终止窗口
示例解法：

  1. class Solution {
  2. public:
  3.     int totalFruit(vector<int>& fruits) {
  4.         int l=0;
  5.         int sub=0;
  6.         int r=0;
  7.         int fruitsB=fruits[r];//两个果篮，起始都是fruits[0]
  8.         int fruitsA=fruits[l];
  9.         int result=0;
  10.         int n=fruits.size();
  11.         while(r<n){
  12.             if(fruitsA==fruits[r]||fruitsB==fruits[r]){//遇到不同的水果停下，记录目前的最大值
  13.                 sub=r-l+1;
  14.                 r++;
  15.                 result=result>=sub?result:sub;
  16.             }
  17.             else{
  18.                 l=r-1;
  19.                 fruitsA=fruits[l];
  20.                 while(l>0&&fruits[l-1]==fruitsA){//将果篮里的水果替换为停下时的水果和它前一位的水果，并且将l移回连续相同的最开端处。
  21.                     l--;  
  22.                 }
  23.                 fruitsB=fruits[r];
  24.                 result=result>=sub?result:sub;
  25.             }
  26.             }return result;
  27.     }
  28. };

76. 最小覆盖子串

未解答
我的解答：https://github.com/kaixuhuang/CPP/blob/master/array/zishuzu.cpp

4.螺旋矩阵

主要考模拟过程
模拟顺时针画矩阵的过程:

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

示例：

螺旋矩阵 II

  1. class Solution {
  2. public:
  3.     vector<vector<int>> generateMatrix(int n) {
  4.         vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
  5.         int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
  6.         int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
  7.         int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
  8.         int count = 1; // 用来给矩阵中每一个空格赋值
  9.         int offset = 1; // 每一圈循环，需要控制每一条边遍历的长度
  10.         int i,j;
  11.         while (loop --) {
  12.             i = startx;
  13.             j = starty;
  15.             // 下面开始的四个for就是模拟转了一圈
  16.             // 模拟填充上行从左到右(左闭右开)
  17.             for (j = starty; j < starty + n - offset; j++) {
  18.                 res[startx][j] = count++;
  19.             }
  20.             // 模拟填充右列从上到下(左闭右开)
  21.             for (i = startx; i < startx + n - offset; i++) {
  22.                 res[i][j] = count++;
  23.             }
  24.             // 模拟填充下行从右到左(左闭右开)
  25.             for (; j > starty; j--) {
  26.                 res[i][j] = count++;
  27.             }
  28.             // 模拟填充左列从下到上(左闭右开)
  29.             for (; i > startx; i--) {
  30.                 res[i][j] = count++;
  31.             }
  33.             // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
  34.             startx++;
  35.             starty++;
  37.             // offset 控制每一圈里每一条边遍历的长度
  38.             offset += 2;
  39.         }
  41.         // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
  42.         if (n % 2) {
  43.             res[mid][mid] = count;
  44.         }
  45.         return res;
  46.     }
  47. };

螺旋矩阵

未解答