977. 有序数组的平方

https://leetcode.cn/problems/squares-of-a-sorted-array/solutions/2769976/977-you-xu-shu-zu-de-ping-fang-by-joker-y0b8q

209. 长度最小的子数组

题目大意

找出一个数组中最短连续的子数组，这个子数组的和要>=s.

解题方法（O(logn)的方法明天更新）

解法称之为虫取法，其实就是双指针。其实看到让连续子数组满足一定条件的很多都用了双指针，比如713. 乘积小于 K 的子数组

时间复杂度是O(N)，空间复杂度是O(1)。

https://leetcode.cn/problems/minimum-size-subarray-sum/solutions/2771847/209-chang-du-zui-xiao-de-zi-shu-zu-by-jo-k9a8

相关题目推荐（明天看）

滑动窗口模板

转载自：作者： 负雪明烛 id： fuxuemingzhu 个人博客： http://fuxuemingzhu.cn/

713. 乘积小于 K 的子数组负雪明烛 大佬写的题解

https://fuxuemingzhu.cn/leetcode/713.html#%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3

《挑战程序设计竞赛》这本书中把滑动窗口叫做「尺取法」，我觉得非常生动形象。因为滑动窗口的两个指针移动的过程和虫子爬动的过程非常像：前脚不动，把后脚移动过来；后脚不动，把前脚向前移动。

我分享一个滑动窗口的模板，能解决大多数的滑动窗口问题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def findSubArray(nums):
    N = len(nums) # 数组/字符串长度
    left, right = 0, 0 # 双指针，表示当前遍历的区间[left, right]，闭区间
    sums = 0 # 用于统计 子数组/子区间 是否有效，根据题目可能会改成求和/计数/乘积
    res = 0 # 保存最大的满足题目要求的 子数组/子串 长度
    while right < N: # 当右边的指针没有搜索到 数组/字符串 的结尾
        sums += nums[right] # 增加当前右边指针的数字/字符的求和/计数
        while 区间[left, right]不符合题意：# 此时需要一直移动左指针，直至找到一个符合题意的区间
            sums -= nums[left] # 移动左指针前需要从counter中减少left位置字符的求和/计数
            left += 1 # 真正的移动左指针，注意不能跟上面一行代码写反
        # 到 while 结束时，我们找到了一个符合题意要求的 子数组/子串
        res = max(res, right - left + 1) # 需要更新结果
        right += 1 # 移动右指针，去探索新的区间
    return res

滑动窗口中用到了左右两个指针，它们移动的思路是：以右指针作为驱动，拖着左指针向前走。右指针每次只移动一步，而左指针在内部 while 循环中每次可能移动多步。右指针是主动前移，探索未知的新区域；左指针是被迫移动，负责寻找满足题意的区间。

模板的整体思想是：

  1. 定义两个指针 left 和 right 分别指向区间的开头和结尾，注意是闭区间；定义 sums 用来统计该区间内的各个字符出现次数；
  2. 第一重 while 循环是为了判断 right 指针的位置是否超出了数组边界；当 right 每次到了新位置，需要增加 right 指针的求和/计数；
  3. 第二重 while 循环是让 left 指针向右移动到 [left, right] 区间符合题意的位置；当 left 每次移动到了新位置，需要减少 left 指针的求和/计数；
  4. 在第二重 while 循环之后，成功找到了一个符合题意的 [left, right] 区间，题目要求最大的区间长度，因此更新 res 为 max(res, 当前区间的长度) 。
  5. right 指针每次向右移动一步，开始探索新的区间。

模板中的 sums 需要根据题目意思具体去修改，本题是求和题目因此把sums 定义成整数用于求和；如果是计数题目，就需要改成字典用于计数。当左右指针发生变化的时候，都需要更新 sums 。

另外一个需要根据题目去修改的是内层 while 循环的判断条件，即： 区间 [left,right] 不符合题意 。

对于本题而言，就是该区间内的元素的乘积 大于等于了 k 。

本人leetcode713的题解

https://leetcode.cn/problems/subarray-product-less-than-k/solutions/2771828/713-cheng-ji-xiao-yu-k-de-zi-shu-zu-by-j-xqi7

符合题目要求的结果增加的是此窗口内的子数组数量，也就是r - l + 1。就是要加上right往后移动一位导致多出来一个元素与前面的数组的元素组成的新的子数组的数量刚刚好就是left right区间的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int left = 0 ,right = 0;//闭区间
        const int N = nums.size();
        long long int products = 1;
        int res = 0;
        while(right < N){
            products *= nums[right];
            while(products >= k && left <= right){//不符合的条件
                products /= nums[left];
                left ++;
            }
            res += right - left + 1;//符合题目要求的结果增加的是此窗口内的子数组数量，也就是r - l + 1。就是要加上right往后移动一位导致多出来一个元素与前面的数组的元素组成的新的子数组的数量刚刚好就是left right区间的长度
            right ++;
        }
        return res;
    }
};

59. 螺旋矩阵 II

https://leetcode.cn/problems/spiral-matrix-ii/solutions/2770510/59-luo-xuan-ju-zhen-ii-by-joker-ek4-lmw4

第二种方法明天看