【代码随想录算法训练营——Day2】数组——209.长度最小的子数组、59.螺旋矩阵II、区间和、开发商购买土地

LeetCode题目链接
https://leetcode.cn/problems/minimum-size-subarray-sum/
https://leetcode.cn/problems/spiral-matrix-ii/
https://kamacoder.com/problempage.php?pid=1070
https://kamacoder.com/problempage.php?pid=1044

题解
209.长度最小的子数组
拿到手题目一想到就是暴力解法，也就是一层for循环遍历开头，一层for循环遍历结尾，计算子数组的和。
看了题解后，采用双指针，本题又可以称为滑动窗口的方法来做，具体做法主要如下：设定j为结尾指针，i为开始指针，以j为结尾向后遍历数组并计算临时和sum，当sum的值>=target时（=target时还要while循环是因为题目要求的是大于等于，如果去掉=号那么将求的是大于，即总和大于target的长度最小的子数组），让开始指针向后移动，同时计算子数组长度，存为result值，result在初始化时要设为最大值。
注意当result仍为初始的最大值时，要返回0，证明此时没有长度的数组满足target条件。

59.螺旋矩阵II
拿到题目第一个想法是区分奇数和偶数，奇数要额外添上中心的那个数，其余就是按照上、右、下、左的顺序来填充，并且每一次为左闭右开区间。但是怎么循环螺旋填充不知道，因此查看题解（请看视频）。
如何控制圈的层数，这里设了3个变量来实现，startx用来确定行初始位置，starty为列，offset为末尾位置，整个正方形不包含中心坐标的循环次数是n/2次，且每次末尾位置为n-offset。且注意采用左闭右开区间的话，每个for循环的末尾值都要留一个值出来。注意每个循环的（包括while和for）的条件，注意循环内部的下标取值，注意控制变量的++，具体看代码写代码即可，也可看视频回顾。

区间和
普通遍历时间复杂度是O(n)，利用前缀和的思想可以降低复杂度，先计算出数组的前缀和，然后对于每个查询，通过前缀和数组快速计算区间和（来自chatGPT）。

开发商购买土地
（之后再补）

代码

//209.长度最小的子数组
#include <iostream>
#include <vector>
using namespace std;

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

int main() {
    Solution s;
    vector<int> nums = { 1,1,1,1,1,1,1,1 };
    int target = 11;
    printf("%d", s.minSubArrayLen(target, nums));
    return 0;
}

//59.螺旋矩阵II
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> result(n, vector<int>(n, 0));
        int startx = 0, starty = 0;
        int offset = 1, count = 1;
        int round = n / 2;
        while (round--) {
            for (int j = starty;j < n - offset;j++) {
                result[startx][j] = count++;
            }
            for (int i = startx;i < n - offset;i++) {
                result[i][n - offset] = count++;
            }
            for (int j = n - offset;j > starty;j--) {
                result[n - offset][j] = count++;
            }
            for (int i = n - offset;i > startx;i--) {
                result[i][starty] = count++;
            }
            startx++;
            starty++;
            offset++;
        }
        if (n % 2 == 1) result[n / 2][n / 2] = count++;
        return result;
    }
};

int main() {
    int n = 4;
    Solution s;
	vector<vector<int>> result = s.generateMatrix(n);
    for (int i = 0;i < result.size();i++) {
        for (int j = 0;j < result[0].size();j++) {
            printf("%d ", result[i][j]);
        }
        printf("\n");
    }
    return 0;
}

//区间和
#include <iostream>
#include <vector>
using namespace std;

int CountSum(vector<int> nums, int i, int j) {
    int sum = 0;
    for (int k = i; k <= j; k++) {
        sum += nums[k];
    }
    return sum;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n, 0), sums(n, 0);
    for (int i = 0;i < n;i++) {
        cin >> nums[i];
    }
    sums[0] = nums[0];
    for (int i = 1;i < n; i++) {
        sums[i] = sums[i - 1] + nums[i];
    }
    int start, end;
    while (cin >> start >> end) {
        //cout << CountSum(nums, start, end) << endl;
        cout << sums[end] - sums[start] + nums[start] << endl;
    }
    return 0;
}