使用前提，单调性

209、长度最小的子数组

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

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

滑动窗口

移动右端点，逐渐缩小左端点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int num = 0;
        int n = nums.size();
        int ans = n + 1;
        int left = 0;
        for(int right = 0; right < nums.size(); ++ right){
            num += nums[right];
            while(num >= target){
                ans = min(ans, right - left + 1);
                num -= nums[left];
                left ++;
            }
            
        }
        return ans == n + 1 ? 0 : ans;
    }
};

713、乘积小于 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

滑动窗口

固定右端点

从左往右检查，符合时，直接增加r-l+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int ans = 0;
        int num = 1;
        int left = 0;
        if(k <= 1){
            return ans;
        }
        for(int right = 0; right < nums.size(); ++ right){
            num *= nums[right];
            while(num >= k){
                num /= nums[left];
                left ++;
            }
            ans += right - left + 1;
        }
        return ans;
    }
};

3、 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

滑动窗口

用哈希表记录字符出现次数，枚举右端点，如果出现次数大于1，右移左端点，没有大于1，记录答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> myMap;
        int l = 0;
        int ans = 0;
        for(int r = 0; r < s.size(); ++ r){
            
            myMap[s[r]] ++;
            
            while(myMap[s[r]] > 1){
                myMap[s[l]] --;
                l ++;
            }
            ans = max(ans, r - l + 1);
        }
        return ans;
    }
};