前言

根据代码随想录使用C++循序渐进学算法

时间复杂度计算

数组

二分查找

704. 二分查找

坚持循环不变量原则！！！

对区间的定义想清楚，区间的定义就是不变量

保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作

左闭右闭

vector<int>& nums

定义target在一个在左闭右闭的区间里，即[left, right]

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)/2;
            if(nums[mid]>target){
                right=mid-1;
            }else if(nums[mid]<target){
                left=mid+1;
            }else if(nums[mid]==target){
                return mid;
            }
        }
        return -1;
    }
};

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

左闭右开

定义target在一个在左闭右开的区间里，即[left, right)

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

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

改进：
mid=(left+right)>>1;
>>

移除元素

27. 移除元素

误区：直接删掉多余的元素

数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖

暴力法

两层for循环，一个for循环遍历数组元素，第二个for循环更新数组

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

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

双指针法

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

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

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

有序数组的平方

977. 有序数组的平方

暴力法

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        for(int i=0;i<nums.size();i++){
            nums[i]*=nums[i];
        }
        sort(nums.begin(),nums.end());
        return nums;
    }
};

时间复杂度：O(n+nlogn)

双指针法

数组有序，则数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间

i指向起始位置，j指向终止位置，定义和nums一样大小的数组result，k指向result数组终止位置

A[i]*A[i]<A[j]*A[j]那么result[k–]=A[j]*A[j];
A[i]*A[i]>=A[j]*A[j]则result[k–]=A[i]*A[i];

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int i=0;
        int j=nums.size()-1;
        int k=j;
        vector<int> result(nums.size(),0);//创建与nums同长，初值均为0的result数组
        for(;i<=j;){
            if(nums[i]*nums[i]<nums[j]*nums[j]){
                result[k--]=nums[j]*nums[j];
                j--;
            }else{
                result[k--]=nums[i]*nums[i];
                i++;
            }
        }
        return result;
    }
};

时间复杂度：O(n)

长度最小的子数组

209. 长度最小的子数组

暴力法

两个for循环不断的寻找符合条件的子序列

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int result=nums.size();
        int sum=0;
        int subLength=0;
        for (int i=0;i<nums.size();i++){
            sum=0;
            for(int j=i;j<nums.size();j++){
                sum+=nums[j];
                if(sum>=target){
                    subLength=j-i+1;
                    result=result<subLength?result:subLength;
                    break;
                }
            }
        }
        return result==nums.size()?0:result;
    }
};

时间复杂度：O(n²)

滑动窗口

只用一个for循环表示滑动窗口的终止位置

窗口的起始位置如何移动：如果当前窗口的值大于等于target了，窗口就要向前移动了（也就是该缩小了）
窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引

滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int i=0;
        int sum=0;
        int sublength=0;
        int result=INT32_MAX;
        for(int j=0;j<nums.size();j++){
            sum+=nums[j];
            while(sum>=target){
                sublength=j-i+1;
                result=result<sublength?result:sublength;
                sum-=nums[i++];//体现滑动窗口的精髓之处，不断变更i（子序列的起始位置）
            }
        }
        return result==INT32_MAX?0:result;
    }
};

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

Q：时间复杂度是O(n)的原因？

A：不要以为for里放一个while就以为是O(n²)，主要得看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是2×n也就是O(n)

螺旋矩阵II

59. 螺旋矩阵 II

坚持每条边左闭右开的原则

每个拐角处让给新的一条边来继续画

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

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 count=1;//用来给矩阵中每一个空格赋值
        int offset=1;//需要控制每一条边遍历的长度，每次循环右边界收缩一位
        int i,j;
        while(loop--){
            i=startx;
            j=starty;
            //下面开始的四个for就是模拟转了一圈
            //模拟填充上行从左到右(左闭右开)
            for(;j<n-offset;j++){
                res[i][j]=count++;
            }
            //模拟填充右列从上到下(左闭右开)
            for(;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++;
        }
        //如果n为奇数的话，需要单独给矩阵最中间的位置赋值
        if(n%2){
            res[mid][mid]=count;
        }
        return res;
    }
};

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

区间和

前缀和

重复利用计算过的子数组之和，从而降低区间查询需要累加计算的次数

统计vec[i]这个数组上的区间和2~5

先做累加，即p[i]表示下标0到i的vec[i]累加之和，有Σ(vec[2]-vec[5])=p[5]-p[1]

p[1]=vec[0]+vec[1];
p[5]=vec[0]+vec[1]+vec[2]+vec[3]+vec[4]+vec[5];
p[5]-p[1]=vec[2]+vec[3]+vec[4]+vec[5];

个人理解就是空间换时间

C++代码面对大量数据读取输出操作，最好用scanf和printf，耗时会小很多

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int n,a,b;
    int presum=0;
    cin>>n;
    vector<int> vec(n);
    vector<int> p(n);
    for(int i=0;i<n;i++){
        cin>>vec[i];//scanf("%d", &vec[i]);
        presum+=vec[i];
        p[i]=presum;
    }
    while(cin>>a>>b){//while(~scanf("%d%d",&a,&b))//如下解释
        int sum;
        if(a==0){
            sum=p[b];
        }else{
            sum=p[b]-p[a-1];
            cout<< sum <<endl;//printf("%d\n",sum);
        }
    }
}

在C语言中，scanf函数返回成功读取的输入项数。当输入有效时，返回值通常为2（因为这里要读取两个整数）。~2在大多数平台上结果为-3，是一个非零值，非零值在布尔上下文中被视为true。当输入无效（如输入非整数字符导致读取失败）时，scanf返回EOF（通常为-1），~-1结果为0，0被视为false。所以这个while循环会一直执行，直到输入无效为止

总结

数组是存放在连续内存空间上的相同类型数据的集合

删除或者增添元素的时候，就难免要移动其他元素的地址

数组的元素是不能删的，只能覆盖