[同向滑动窗口] 209. 长度最小的子数组 713. 乘积小于 K 的子数组 3. 无重复字符的最长子串

同向双指针

该文结合灵神讲解进行编码：https://www.bilibili.com/video/BV1hd4y1r7Gq

该类滑动窗口一般符合某种单调性。

当不满足条件时左指针后移，当满足条件时右指针后移。

假设数组长度为 n，左指针最多移动 n 次，右指针最多移动 n 次，因此时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。

209. 长度最小的子数组

https://leetcode.cn/problems/minimum-size-subarray-sum/

Solution

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int l = 0, r = 0;
        int sum = 0;
        int ans = nums.length + 1;
        while (r < nums.length) {
            sum += nums[r];
            while (sum >= target) {
                ans = Math.min(r - l + 1, ans);
                sum -= nums[l++];
            }
            r++;
        }
        return ans <= nums.length ? ans : 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

713. 乘积小于 K 的子数组

https://leetcode.cn/problems/subarray-product-less-than-k/

Solution

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) {
            return 0;
        }
        int l = 0, r = 0;
        int prod = 1;
        int ans = 0;

        while (r < nums.length) {
            prod *= nums[r];
            while (prod >= k) {
                prod /= nums[l++];
            }
           ans += r - l + 1; // key point
           r++;
        }

        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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

https://leetcode.cn/problems/longest-substring-without-repeating-characters/

Solution（哈希表+双指针）

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length()<=1){
            return s.length();
        }
        char[] chars = s.toCharArray();
        int[] hash = new int[128];
        int l = 0, r = 0;
        int ans = 0;

        while (r < s.length()) {
            hash[chars[r]]++;
            while (hash[chars[r]] > 1) {
                hash[chars[l++]]--;
            }
            ans = Math.max(ans, r - l + 1);
            r++;
        }

        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22