LeetCode209

2025-01-23 18:31:09 星期四

题目描述：力扣209
文档讲解：代码随想录(programmercarl)209. 长度最小的子数组
视频讲解：《代码随想录》算法视频公开课：拿下滑动窗口！ | LeetCode 209 长度最小的子数组

代码随想录视频内容简记

这道题目仍然是用双指针的思想，如果是暴力解法，用两个for循环，但是双指针的思想就是要用一个for循环来解决问题，所以时间复杂度为\(O(n)\)

梳理

1. j是起始位置还是终止位置

2. 计算滑动窗口元素的和

3. 更新数组最小长度subl并缩小滑动窗口

4. 关于时间复杂度\(O(n)\)

   这个题真是感觉抽象

大致代码内容

1. 首先是关于for(j = 0; j < nums.size(); j++)中的这个j到底指向的是滑动窗口的起始位置还是终止位置？如果是起始位置，那么终止位置就要依然跟着从0开始向后遍历，就和暴力解法一样了。而如果是终止位置，那么只需要采取策略移动起始位置，就可以不断缩小滑动窗口的范围。所以，这里的j是终止位置

2. 计算滑动窗口内部的和需要使用sums = sums + nums[j]

3. 更新数组最小长度subl并缩小滑动窗口。这是滑动窗口内层的while()循环，是while(sums >= target)。如何更新数组的最小长度subl？首先需要在开始定义subl为一个Max值，之后不断进行subl = min (subl, j - i)。那么如何缩小滑动窗口呢？首先需要sums减掉当前位置的nums[i]，之后进行i++操作。

LeetCode测试

这个运行了好多遍一直报错，是有个小坑的。

报错

1. 首先是题目描述中说明了“如果不存在符合条件的子数组，返回 0 ”

   所以这个需要看清楚，在return的时候写清楚0的情况

2. 在梳理的第三步

   刚开始看视频我没注意写的是“缩小滑动窗口并更新数组最小长度subl”，于是代码就长这样，一直报错，找不出来问题

while (sum >= target) {
	// 缩小滑动窗口
	sum -= nums[i];
	i++;
	// 更新数组最小长度
	result = j - i + 1;
	subl = min(subl, result);
}

按照k哥的方法，全删了重新写了之后发现这样有个问题就是每次的result计算会没有来得及计算刚开始i值，其就进行了i++操作，这样显然是不对的，于是修改之后

while (sum >= target) {
	sum -= nums[i];
	result = j - i + 1;
	subl = min(subl, result);
	i++;
}

这样就对了，然后现在再一看，就是先“更新数组最小长度subl并缩小滑动窗口”，于是就可以整理的下

while (sum >= target) {
	// 更新数组最小长度
	result = j - i + 1;
	subl = min(subl, result);
	// 缩小滑动窗口
	sum -= nums[i];
	i++;
}

至于为什么非得按照先更新数组最小长度，再缩小滑动窗口，我的理解应该就是上面的Bug。如果先缩小滑动窗口显然会跳过某些i值，就肯定不对了

滑动窗口代码

这个代码的时间复杂度是\(O(n)\)，其实确实不太理解，但是k哥讲的是

看每一个元素被操作的次数，每个元素在滑动窗口进来操作一次，出去操作一次，每个元素都被操作两次，所以时间复杂度是\(2\times n\)也就是\(O(n)\)

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int i = 0, sum = 0, subl = INT32_MAX, result;
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            while (sum >= target) {
                // 更新数组最小长度
                result = j - i + 1;
                subl = min(subl, result);
                // 缩小滑动窗口
                sum -= nums[i];
                i++;
            }
        }
        return subl == INT32_MAX ? 0 : subl;
    }
};

LeetCode59

题目描述：力扣59
文档讲解：代码随想录(programmercarl)59.螺旋矩阵II
视频讲解：《代码随想录》算法视频公开课：拿下螺旋矩阵！LeetCode：59.螺旋矩阵II

代码随想录视频内容简记

梳理

1. 坚持循环不变量原则

   这道题目，并没有用到二分法、双指针，但是其思想是和二分法那道题目是一样的。就是要明确在循环中，使用统一的规则进行判断，从而避免各种对边界条件的if的复杂讨论。具体到这道题目中，就是使用左闭右开的规则。

2. 确定初始位置和确定每一条边循环之后的终止位置

3. 循环条件。这个循环条件很重要，刚开始就写错了

4. 对生成的矩阵的边的长度进行讨论，具体是奇数还是偶数

大致代码内容

1. startx = 0, starty = 0，首先给初始位置赋值

2. offset = 1给终止位置赋值

3. loop = n / 2， while(loop--)，这里的判断条件是适用于矩阵边长为偶数的情况，还有一个奇数的情况就是放在最后才加上的

4. 四个for循环。

5. 最后需要对边为奇数的情况进行单独讨论nums[mid][mid] = count

LeetCode测试

有几个坑

标签：59,nums,209,随想录,++,while,滑动,subl,loop
From： https://www.cnblogs.com/bnbncch/p/18687043