数组理论基础

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

C++中，二维数组的内存空间也是线性的连续的

代表性算法

二分查找

704. 二分查找 - 力扣（LeetCode）

对于比较简单的二分查找来说，重点就是while里的条件和l,r指针的移动

第一种写法【l,r】内搜索

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l=0;
        int r=nums.size()-1;
        while(l<=r){
            int mid=l+(r-l)/2;
            if(nums[mid]==target)
                return mid;
            else if(nums[mid]<target){
                l=mid+1;
            }
            else{
                r=mid-1;
            }
        }
        return -1;
    }
};

第二种写法【l,r)内搜索?

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l=0;
        int r=nums.size();
        while(l<r){
            int mid=l+(r-l)/2;
            if(nums[mid]==target)
                return mid;
            else if(nums[mid]<target){
                l=mid+1;
            }
            else{
                r=mid;
            }
        }
        return -1;
    }
};

移除元素

27. 移除元素 - 力扣（LeetCode）

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow=0,fast=0;
        for(;fast<nums.size();fast++){
            if(nums[fast]!=val)
                nums[slow++]=nums[fast];
        }
        return slow;
    }
};

有序数组的平方

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

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int l=0,r=nums.size()-1;
        int n=nums.size()-1;
        vector<int> ans(nums.size(),0);
        
        while(l<=r){
            if(nums[l]*nums[l]>nums[r]*nums[r] ){
               ans[n--]=nums[l]*nums[l];
                l++;
            }
            else{
                ans[n--]=nums[r]*nums[r];
                r--;
            }
        } 
        return ans;
    }
};

长度最小的子数组

209. 长度最小的子数组 - 力扣（LeetCode）

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = 100005;
        int sum = 0; // 滑动窗口数值之和
        int i = 0; // 滑动窗口起始位置
        int Length = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
            while (sum >= s) {
                Length = (j - i + 1); // 取子序列的长度
                result = min(result,Length);
                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == 100005 ? 0 : result;
    }
};

螺旋矩阵

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

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int> >res(n,vector<int>(n,0)); //二维数组进行初始化
        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 cnt=1; //用来给矩阵中每一个空格赋值
        int offset=1; //每一圈循环，需要控制每一条边遍历的长度

        int i,j;

        while(loop--){
            i=startX;
            j=startY;

            //下面开始的四个for就是模拟转了一圈
            //一定要注意，从始至终区间都是左闭右开

            //从左到右
            for(j=startY;j<startY+n-offset;j++){
                res[startX][j]=cnt++;
            }

            //从上到下
            for(i =startX;i<startX+n-offset;i++){
                res[i][j]=cnt++;
            }

            //从右到左
            for(;j>startY;j--){
                res[i][j]=cnt++;
            }

            //从下到上
            for(;i>startX;i--){
                res[i][j]=cnt++;
            }

            //第二圈开始的时候，起始位置要各自+1
            startX++;
            startY++;

            offset+=2; //少了左右两个格儿
        }

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