当前位置：首页 > article >正文

【算法day2】数组：滑动窗口、前缀和及指针控制

article 2024/11/29 19:30:44

题目引用

209.长度最小的子数组
区间和
螺旋矩阵II

1.长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的
子数组
[numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：

输入：target = 4, nums = [1,4,4]
输出：1
示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

这里我们看一下题目：题目要求我们找到最短的 >=target 的数组并且返回它的长度。大家见到这种题目的时候可能下意识的就会想到我使用嵌套循环，从每个数组的位置出发寻找符合题意的数组并且不断更新最短的长度，这样当然是可以的，但是时间复杂度就是 O(N^2) 了。那么怎么减少时间复杂度呢？这就要引出今天的第一个算法： 滑动窗口 。

首先我们还是设立两个指针，一个快指针 fast ，一个慢指针 slow ，都设立在起点
初始化
然后定义 result=INT_MAX ， fast 到 slow 的区间和为 sum=0 ，变化后的区间和为 tmp=0 。

当 sum>=target 时，用 tmp 记录当前 fast 到 slow 的长度，更新 result ，然后将末尾 slow 位置的值减掉， slow 向前走寻找新的子区间，直到fast到达末尾循环结束。
进入循环

最后附上代码

int minSubArrayLen(int target, vector<int>& nums) {
        int slow=0;
        int result=INT_MAX;
        int sum=0;
        int tmp=0;
        for(int fast=0;fast<nums.size();fast++){
            sum+=nums[fast];
            while(sum>=target){
                tmp=(fast-slow+1);
                result=min(tmp,result);
                sum-=nums[slow++];
            }
        }

        return result==INT_MAX?0:result;
    }

值得注意的是，我们的sum有可能到循环结束都没有更新过result，所以最后返回时需要特判一下，避免这种情况。

区间和

题目描述
给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。
输入描述
第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间下标：a，b （b > = a），直至文件结束。
输出描述
输出每个指定区间内元素的总和。
输入示例

输出示例

3
9

我们来分析一下题目
我们得到了一个长度为n的随机数组，需要计算从这个区间里面所有数的和，最简单的解法当然还是嵌套循环，每次从区间的左加到区间的右，但是依然需要经历两层循环，不美。
让我们看看怎么利用前缀和解决这个问题。
前缀和 就是从数组的第一个位置开始累加到当前位置的数值就叫做前缀和。那么我们怎么获取到前缀和呢？
很简单，在我们接受数据时额外定义一个数组和一个变量，用来记录当前位置的前缀和，而这个数组就叫做前缀和数组，当题目给出需要的区间和时，我们只需要将右边界所在的前缀和减去左边界所在的位置前一位的前缀和就能得出答案，当然如果左边界是0的话，我们直接取右区间数值即可。
以案例一为例
初始化

可能有人会疑问，为什么要减左边界的前一位呢？
因为前缀和是从数组0位置累加到自己本身的，如果是直接减去左边界位置的前缀和，就相当于把左边界自己也减掉了，也就与结果相差左边界本身的值了。
那么我们来看代码：

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, a, b;
    cin >> n;
    vector<int> vec(n);
    vector<int> p(n);
    int presum = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &vec[i]);
        presum += vec[i];
        p[i] = presum;
    }

    while (~scanf("%d%d", &a, &b)) {
        int sum;
        if (a == 0) sum = p[b];
        else sum = p[b] - p[a - 1];
        printf("%d\n", sum);
    }
}

螺旋矩阵

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]
示例 2：

输入：n = 1
输出：[[1]]

来说一下思路
题目只给我们一个n，要求我们返回已经旋转好的二维数组，那么我们发现数组会绕着外围一直旋转，直到转到数组中心，那么总共转几圈呢？
去掉中心只旋转了n/2 圈。
所以我们需要绕着数组一直旋转n/2圈，并且需要一个数每填一次就++，并且在内圈旋转时需要重新定位位置再次旋转，那么代码就不难了。

vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> vv(n,vector<int>(n,0));
        int x=0,y=0;
        int loop=n/2;
        int count=1;
        int offset=1;
        int i,j;
        while(loop--){
            i=x,j=y;
            for(;j<y+n-offset;j++){
                vv[i][j]=count++;
            }

            for(;i<x+n-offset;i++){
                vv[i][j]=count++;
            }

            for(;j>y;j--){
                vv[i][j]=count++;
            }

            for(;i>x;i--){
                vv[i][j]=count++;
            }

            x++,y++;
            offset+=2;
        }
        int mid=n/2;
        if(n%2) vv[mid][mid]=count;

        return vv;
    }