当前位置：首页 > article >正文

面试经典150题——滑动窗口

article 2025/1/4 17:42:32

文章目录

1、长度最小的子数组
- 1.1 题目链接
- 1.2 题目描述
- 1.3 解题代码
- 1.4 解题思路
2、无重复字符的最长子串
- 2.1 题目链接
- 2.2 题目描述
- 2.3 解题代码
- 2.4 解题思路
3、串联所有单词的子串
- 3.1 题目链接
- 3.2 题目描述
- 3.3 解题代码
- 3.4 解题思路
4、最小覆盖子串
- 4.1 题目链接
- 4.2 题目描述
- 4.3 解题代码
- 4.4 解题思路

1、长度最小的子数组

1.1 题目链接

点击跳转到题目位置

1.2 题目描述

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

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

1 <= target <= 10⁹
1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁴

1.3 解题代码

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int right = -1;
        int n = nums.length;
        int sum = 0;
        int min_len = n + 1;
        while(right < n - 1){
            ++right;
            sum += nums[right];
            while(sum >= target){
                min_len = Math.min(min_len, right - left + 1);
                sum -= nums[left];
                left++;
            } 
        }
        if(min_len == n + 1){
            return 0;
        }
    return min_len;
    }
}

1.4 解题思路

使用滑动窗口解决问题。
滑动窗口向右移动，右指针移动，总和增加的，一旦总和大于等于目标值，左指针开始移动，每次移动前都更新一下长度，然后更新sum值（减少），直到sun值小于target后重新开始移动右指针。

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

2.1 题目链接

点击跳转到题目位置

2.2 题目描述

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

提示：

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

2.3 解题代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int left = 0;
        int right = -1;
        int n = s.length();
        int len = 0;
        Set<Character> hash = new HashSet<Character>();
        while(right < n - 1){
            ++right;
            char ch = s.charAt(right);
            if(!hash.contains(ch)){
                hash.add(ch);
            } else{
                while(hash.contains(ch)){
                    hash.remove(s.charAt(left));
                    ++left;
                }
                hash.add(ch);
            }
            len = Math.max(len, right - left + 1);
        }
    return len;
    }
}

2.4 解题思路

滑动窗口解决该问题。
右指针右移，如果当前所指的字符不在集合里面，直接把该字符添加进字符中；如果当前所指的字符在集合里面，去除左指针所指的字符，并右移动，直到右指针所指的字符在集合中查询不到，最后再将右指针所指的字符添加进去。
再上述操作执行完毕后更新一下最长的长度。

3、串联所有单词的子串

3.1 题目链接

点击跳转到题目位置

3.2 题目描述

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如，如果 words = [“ab”,“cd”,“ef”]，那么 “abcdef”， “abefcd”，“cdabef”， “cdefab”，“efabcd”，和 - “efcdab” 都是串联子串。 “acdbef” 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

提示：