长度最小的子数组

209. 长度最小的子数组 - 力扣（LeetCode）

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

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

此题可以使用滑动窗口进行求解。首先注意到所有元素均为正整数，所以往窗口内添加元素总会让元素之和变大（单调性）。因此需要判断窗口内的元素之和是否大于target，如果大于则向右移动左侧指针，直到窗口内元素和小于target，否则向右移动右指针，直到窗口内元素和再大于target对左指针进行相同操作。这里左、右指针均最多移动$N$次，所以时间复杂度为$O(N)$，空间复杂度为$O(1)$。

需要注意没有满足条件的子数组返回0，需要对此进行判断。

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

乘积小于K的子数组

713. 乘积小于 K 的子数组 - 力扣（LeetCode）

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

示例 1：

1
2
3
4
输入：nums = [10,5,2,6], k = 100
输出：8
解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2]、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。

示例 2：

1
2
输入：nums = [1,2,3], k = 0
输出：0

提示:

  • 1 <= nums.length <= 3 * 10^4
  • 1 <= nums[i] <= 1000
  • 0 <= k <= 10^6

与上一题类似，移动右指针r，考虑当窗[l, r]满足条件时，则表明窗口为[l+1, r]...[r, r]的子数组均满足条件；不满足条件时，则右移左指针缩小乘积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0; // 要排除0、1的情况，否则下面prod >= k会导致left超过right
        int prod = 1, left = 0;
        int ans = 0;
        for (int right = 0; right < nums.length; ++right) {
            prod *= nums[right];
            while (prod >= k) {
                prod /= nums[left];
                left++;
            }
            ans += right - left + 1;
        }
        return ans;
    }
}

无重复字符的最长字串

3. 无重复字符的最长子串 - 力扣（LeetCode）

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

示例 1:

1
2
3
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

1
2
3
4
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

  • 0 <= s.length <= 5 * 10^4
  • s 由英文字母、数字、符号和空格组成

与先前的题目类似，该题需要额外引入哈希表对滑窗内的字符个数进行计数，移动右指针，并将接收到的字符录入哈希表，当统计到某个字符已经存在哈希表内时，则需要移动左指针直至找到该字符，此时便得到了一个无重复字符的字符串，记录长度并对比保存。算法时间复杂度为$O(N)$，空间复杂度取决于出现字符的种类个数，可视为$O(1)$。