数组part02

2024年8月1日，今天学习了数组的第二部分。
1.巩固了昨天的双指针问题，即滑动窗口/双指针；注意，双指针是为了减少for循环，使用的时候小心循环的写法和快慢指针的增长方法。
2.学习了数组模拟的螺旋矩阵问题，注意循环不变量；
3.学习了前缀和的方法，前缀和常用来解决区间和问题，其实是避免重复读取计算数组中的值，提前算好。

5. 209长度最小的子数组（滑动窗口/双指针）

题目：给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

暴力解法两层for循环，第一个for遍历子数组起点，第二个for遍历终点。

要想变成一个for循环，考虑使用双指针，两个指针都只需要遍历一次，两个指针之间的即为子数组/滑动窗口。很明显：

i：起始位置，窗口大于等于s，向前移动

j：结束位置，窗口不到s，向后移动。

1. 双指针问题考虑循环的写法，一般是fast指针做循环的索引，所以j是for中的index。
2. j在for中更新了，如何更新i呢？应该是每次动了j，都要把sum和target比较，若是sum>target，就移动i。但是这里不能是if(sum>target),应该是while(sum>target)，因为需要不停的移动i，直到sum<target。

注意：双指针问题中两个ptr分别是怎么动的，是在for动呢，还是for里头，for里头的话，是比较一次动一次（if）就好，还是多次比较多次动直至满足条件（while）。

int minSubArrayLen(int target, vector<int> &nums)
    {
        int result = INT32_MAX;
        int sum = 0;       // 滑动窗口数值之和
        int i = 0;         // 滑动窗口起始位置
        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++)
        {
            sum += nums[j];
            // 每次更新 i，并不断比较子序列是否符合条件
            while (sum >= target)
            {
                subLength = (j - i + 1); // 取子序列的长度
                result = result < subLength ? result : subLength;
                sum -= nums[i++]; //滑动窗口的精髓:不断变更i
            }
        }
        // 如果result没有被赋值，返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }

6. 59 螺旋矩阵

题目：给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

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

要写成代码多次循环，就要坚持循环不变量原则，不难发现横竖左右四条边都要左闭右开，因此对应的图如下：

那么代码至少需要知道以下几个量：

1. 循环几次？这个就是最外层的循环，即循环几圈。

   1. 举例子，3*3需要1次加一个正中间的点，4*4需要2次。
   2. int loop = n / 2;，n为奇数时中间的点需要单独处理。
   3. mid = n / 2; 矩阵中间的位置，例如：n为3,中间的位置就是(1，1)。

2. 每次的起始位置和终止位置？

   1. 首先，明确左上角此圈开始的位置，每次都要+1，所以可以设置一个startx = 0, starty = 0，即每循环一个圈的起始位置。
   2. 上边从左到右：for (j=starty ; j<n-offset; j++)
   3. 右列从上到下:for (i; i < n - offset; i++)
   4. 下边从右到左：for (; j > starty; j--)，承接上头的j，此时的j=n-offset。
   5. 左列从下到上：for (; i >startx; i--)

3. 每一圈里每一条边遍历的长度?

   通过一个变量offset来控制。最开始offset为1，即最外圈应该是n-offset那么长，之后每一圈的边都要减2，而起始位置startx和starty都加了1，那么控制结尾的offset只需要加1即可。

7. 区间和（前缀和：避免数组重复读取计算，借助额外空间）

题目：给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。

暴力解法：首先读入，需要[1,5]之间的，那就再循环1到5之间的数值。所以有多少个查询，就有多少次循环。需要注意不知道有多少次查询，ACM形式读入数据时采用这种方法：

while (cin >> a >> b) {}

前缀和解法：来一个算一个太重复了，首先就把每个前缀和都算出来，用哪个取哪个。p[i] 表示 下标 0 到 i 的 vec[i] 累加 之和。

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);
    }
}

1. 注意不知道多少行时，读取数据的方法。

2. 大数据量使用scanf等，不用cin。

   ~scanf("%d%d", &a, &b):

   1. scanf 函数返回成功读入的数据项数，读入数据时遇到了“文件结束”则返回EOF。
   2. scanf ( "%d %d" ,&a,&b)：如果a和b都被成功读入，那么返回值就是2；如果只有a被成功读入，返回值为1；
      如果a和b都未被成功读入，返回值为0；如果遇到错误或遇到end of file，返回值为EOF。
   3. EOF的值为-1，其取反的的值为0（-1的补码表示全是1，按位取反后全是0）。

今日古诗

点绛唇·感兴

王禹偁〔宋代〕

雨恨云愁，江南依旧称佳丽。水村渔市，一缕孤烟细。
天际征鸿，遥认行如缀。平生事，此时凝睇，谁会凭栏意。

这算是王禹偁传世的唯一词作了。此词以清丽的笔触、沉郁而高旷的格调，即事即目，描绘了江南水乡的风物景色，并通过描绘江南雨景，寄寓了词人积极用世、渴望有所作为的政治理想和怀才不遇的苦闷情怀。全词寓情于景，因情绘景，感情质朴，风格清丽。