滑动窗口

题目中关键字是有连续、数组等字眼，可以考虑使用滑动窗口。

但如果数组中有负数，就不能用滑动窗口解决，可以考虑前缀和的方法。

LeetCode题目总结

和为s的连续正数序列

滑动窗口

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

思路：

选取一个点i，让j一直走，直到j>target，若都没有找到和为target的连续序列，则证明前面选的i之后没有满足条件的连续数，因此i向下一位移动。循环往复，直到i的上界（i <= target/2）时。

用sum记录累加的和，如果sum<target，j还能往右走，sum不断累加。直到sum>target，都没有找到连续的数和为target，则证明以i开头没有连续的数，则sum-i，i继续下一位，i++。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

vector<vector<int>> findContinuousSequence(int target) {
       int i = 1;
       int j = 1;
       int sum  = 0;
       
       vector<vector<int>>ans;
       while(i <= target/2){
           if(sum < target){
               sum += j;
               j++;
           }
           else if(sum > target){
               sum -= i;
               i++;
           }
           else{
               vector<int>vec;
               for(int k = i; k < j; k++){
                   vec.push_back(k);
               }	
               ans.push_back(vec);
               sum -= i;
               i++;
           }
       }
       return ans;
   }

剑指 Offer II 009. 乘积小于 K 的子数组

https://leetcode.cn/problems/ZVAVXX/

思路：

如果符合条件(乘积 <k)，则不断右移，并不断计算子数组的个数 j - i + 1；

否则左边窗口移动，i++， 缩小窗口范围，sum /= nums[i] 保持和为最新的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int numSubarrayProductLessThanK(vector<int>& nums, int k) {
    int i = 0, j = 0, sum = 1;
    int ans = 0;
    int n = nums.size();
    while(j < n) {
        sum *= nums[j];
        while(i <= j && sum >= k) {
            sum /= nums[i];
            i++;
        } 
        ans += j - i + 1;
        j++;
        
    }
    return ans;
}

剑指 Offer II 008. 和大于等于 target 的最短子数组

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

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

示例 1：

1 2 3

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

1
2
3
4
5
6
7
8
9
10
11
12

int minSubArrayLen(int target, vector<int>& nums) {
    int left = 0, n = nums.size(), ans = n + 1, sum = 0;
    for(int right = 0; right < n; right++) {
        sum += nums[right];
        while(sum >= target) {
            sum -= nums[left];
            ans = min(ans, right - left + 1);
            left++;
        }
    }
    return ans == n + 1 ? 0 : ans;
}

https://leetcode.cn/problems/2VG8Kg/

https://leetcode.cn/problems/ZVAVXX/

• ← Previous Post
• Next Post →