1. 数组的基础定义

数组的下标是从0开始的
数组中的地址是连续的

要删除数组中的元素只能用替换去实现，无法直接删去

2. 二分法

2.1 使用条件

在求解寻找数组中的元素，或者满足条件的值会出现在数组的范围内（如求平方根）等内容时可使用；

使用时数组需满足如下条件（或变化后）：

数组升序或者降序排列，即有序数组
数组中无重复项的出现

2.2 时间复杂度

暴力解法时间复杂度：O(n)
二分法时间复杂度：O(logn)

2.3 主要思想

通过在有序数组中划分中间值，判断所求值与中间值之间的关系，较暴力解法可以直接排除掉一些不在范围之内的比较，提升了运行效率。

有序数组：索引定位数据，索引的大小关系即为数组元素的大小关系。

要定义的几个参数：

开始位置：left = 0;（数组下标索引从0开始）

结束位置：right = nums.size() - 1;

中间值：mid = left + ((right - left) >> 1) (位运算，可以防止数组越界现象出现)

2.4 注意点

区间的划分

// 原因是此时mid的值一定不是我们寻找的，否则不会出现在这个循环，那么我们在移动的时候也可以不考虑这个值
if (nums[middle] > target) {
                right = middle - 1; // target 在左区间，所以[left, middle - 1]
            }

循环终止判断条件

1	while (left <= right) // 当left==right，区间[left, right]依然有效，所以用 <=

2.5 完整代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0; //定义数组的左节点
        int right = nums.size()-1; //定义数组的右节点
        while(left <= right) {
                int mid = left + (right - left) / 2; //定义中间点，防止索引越界
                if(target < nums[mid]) {
                    right = mid - 1; // 目标值在左区间
                }
                else if(target > nums[mid]) {
                    left = mid + 1; // 目标值在右区间
                }
                else if(target == nums[mid]) {
                    return mid;
                }
        }
        return -1;
    }
};

3. 双指针法

3.1 使用条件

需要双重遍历：需要实现先定位元素，再实现元素修改的题目，都可以用双指针法。

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

定义快慢指针

快指针：寻找新数组的元素，新数组就是不含有目标元素的数组
慢指针：指向更新新数组下标的位置

3.2 复杂度

时间复杂度：O(n)
空间复杂度：O(1)

3.3 主要思想

fastIndex指针用来寻找要删除的值，slowIndex指针用来定位要修改的值

在删除元素这道题目中，体现在fastIndex在一直在移动，而通过判断if(nums[fastIndex] != val) 来控制是否替换，相当于核心思想是在原有的数组上替换了一个新的数组，这个数组元素所要满足的条件就是if判断的条件。

3.4 注意点

用双指针移动删除元素可以使得时间复杂度下降，只需要一个循环遍历即可，一个指针用来寻找删除元素，另一个指针用来实现替换操作。这里用for循环，不用while循环的原因是： for循环一般用于有终止条件，变量只有一个并且判断条件可以简单的用一个boolean表达式表现出来，而while循环主要用于迭代条件较为复杂，例如二分查找法的情况，左右节点都需要根据不同情况进行更新。而在双指针中，fastIndex指针是无条件一直向前运行的，我们只需在循环体中控制slowIndex指针即可。

3.5 代码实现

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        //双指针删除元素 fast指针用于搜索，slow指针用于替换值
        int slowIndex = 0;
        //结束条件，搜索指针搜索完成。
        for(int fastIndex = 0; fastIndex < nums.size(); fastIndex++ ) {
            if(nums[fastIndex] != val) {
                nums[slowIndex ++] = nums[fastIndex];
            }
        }
        return slowIndex;
    }
};

双指针Pro（相向双指针）：

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int leftIndex = 0;
        int rightIndex = nums.size() - 1;
        while (leftIndex <= rightIndex) {
            // 找左边等于val的元素
            while (leftIndex <= rightIndex && nums[leftIndex] != val){
                leftIndex++;
            }
            // 找右边不等于val的元素
            while (leftIndex <= rightIndex && nums[rightIndex] == val) {
                rightIndex-- ;
            }
            // 将右边不等于val的元素覆盖左边等于val的元素
            if (leftIndex < rightIndex) {
                nums[leftIndex++] = nums[rightIndex--];
            }
        }
        return leftIndex;   // leftIndex一定指向了最终数组末尾的下一个元素，原因是因为有几个val就代表被中断了几次，此时只有单向运动，长度就会缩减
    }
};

4. 滑动窗口

4.1 使用条件

数组中满足条件的最小子数组。一般求解需要经过两个步骤，首先需要先判断出有哪些满足条件的情况存在。之后再去这些满足条件存在中求解最优。

一般会出现如下条件需要去定义：

滑动窗口的起始点（可以理解为快指针）
滑动窗口的终止点（可以理解为慢指针）
滑动窗口内条件的表示：例如最大值，元素相等之类的

4.2 复杂度

时间复杂度：O(n)

主要是看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是 2 × n 也就是O(n)。

空间复杂度：O(1)

4.3 主要思想

时间复杂度的优化其实可以简略的看成循环的优化，而循环优化的最主要思想之一就是能否对相关项进行合并。换而言之就是变量之间能不能够相互解释。

对比暴力解法和滑动窗口能够发现其精妙之处：

暴力解法：判断满足条件的子数组存在（一层遍历） ===> 子数组内判断是否最优（存在遍历中的遍历）===> 比较
滑动窗口：移动终止点去判断是否存在 ===> 移动起始点去求最优

这时候我们会发现，其实滑动窗口用了条件这个东西同时判断了两个值，而暴力解法则是在数组内部又进行了一个数组的判断，所以我们其实可以用两个点窗口大小去表示条件的时候，这样做就相当于实现了循环次数的减少。

4.4 注意点

求和的操作很巧妙，融合在一起表现在头指针移动会影响到数组和值，尾指针移动也能够影响到数组的和值。
数组最小长度的迭代更新，首先直接替换肯定不行，因为无法确定最后一个就是最小的。然后自己比自己求最小也不行，因为你需要一个0的初始值。所以在这里需要引入一个新的变量，result = INT32_MAX。

INT32_MAX是一个常量，表示极大值，主要作用是有值时第一次比较时一定会被替换成result, 如果没有被比较到，那么最后返回结果用三元运算符返回0即可。

4.5 代码实现

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        //因为其要变化两个量：最小数组的开始值，数组的长度，所以可能需要两次for循环来找到答案
        //滑动窗口法:将结果看成是变化，找到大于target的数组，之后不断缩小，贪心算法？
        int fastIndex = 0, slowIndex = 0, sum = 0, length = 0, result = INT32_MAX;
        //小于等于是考虑末值的条件
        for(;fastIndex < nums.size(); fastIndex++) {
            //求和放在和
            sum += nums[fastIndex];
            while(sum >= target) {
                length = (fastIndex - slowIndex + 1) ;
                result = result > length ? length : result;
                sum -= nums[slowIndex];
                slowIndex++;
            }
        }
        return result == INT32_MAX ? 0 : result;
    }
};

5. 螺旋矩阵

5.1 使用条件

题目告诉你要用螺旋矩阵，没有什么特别算法的意思，更多的是体现了一种对语言的运用和流程的表述

5.2 复杂度

5.3 主要思想

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

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

由外向内一圈一圈这么画下去。

5.4 注意点

开闭区间的判断

5.5 代码实现

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
        int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
        int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
        int count = 1; // 用来给矩阵中每一个空格赋值
        int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
        int i,j;
        while (loop --) {
            i = startx;
            j = starty;

            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
            for (j = starty; j < n - offset; j++) {
                res[startx][j] = count++;
            }
            // 模拟填充右列从上到下(左闭右开)
            for (i = startx; i < n - offset; i++) {
                res[i][j] = count++;
            }
            // 模拟填充下行从右到左(左闭右开)
            for (; j > starty; j--) {
                res[i][j] = count++;
            }
            // 模拟填充左列从下到上(左闭右开)
            for (; i > startx; i--) {
                res[i][j] = count++;
            }

            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
            startx++;
            starty++;

            // offset 控制每一圈里每一条边遍历的长度
            offset += 1;
        }

        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
        if (n % 2) {
            res[mid][mid] = count;
        }
        return res;
    }
};

数组

1. 数组的基础定义

2. 二分法

相关题目

2.1 使用条件

2.2 时间复杂度

2.3 主要思想

2.4 注意点

2.5 完整代码

3. 双指针法

相关题目

3.1 使用条件

3.2 复杂度

3.3 主要思想

3.4 注意点

3.5 代码实现

4. 滑动窗口

相关题目

4.1 使用条件

4.2 复杂度

4.3 主要思想

4.4 注意点

4.5 代码实现

5. 螺旋矩阵

相关题目

5.1 使用条件

5.2 复杂度

5.3 主要思想

5.4 注意点

5.5 代码实现