滑动窗口经典问题

2023-12-13 15:47:27

关卡名

滑动窗口高频问题

我会了??

内容

1.掌握最长子串问题

??

2.理解长度最小的子数组问题

??

3.掌握盛水最多的容器问题

??

4.理解异位词问题如何解决

??

1 最长子串专题?

先来看一道高频算法题:无重复字符的最长子串。具体要求是给定一个字符串 s ,请你找出其中不含有重复字符的最长子串的长度。例如,输入: s = "abcabcbb" 则输出3,因为无重复字符的最长子串是 "abc",所以其长度为3。
怎么做后面再说,如果再变一下要求,至多包含两个不同字符的最长子串,该怎么做呢?
再变一下要求,至多包含 K 个不同字符的最长子串,该怎么做呢?
到这里是否感觉,这不在造题吗?是的!上面就分别是LeetCode3、159、340题,而且这几道题都可以用滑动窗口来解决。学会之后,我们就总结出滑动窗口的解题模板了。
接下来,我们就一道一道看。

1.1 无重复字符的最长子串?

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

输入: s = "abcabcbb"

输出: 3

解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

要找最长子串,必然要知道无重复字符串的首和尾,然后再从中确定最长的那个,因此至少两个指针才可以,这就想到了滑动窗口思想。即使使用滑动窗口,深入分析会发现具体处理起来有多种方式。这里介绍一种经典的使用Map的思路。
我们定义一个K-V形式的map,key表示的是当前正在访问的字符串,value是其下标索引值。我们每访问一个新元素,都将其下标更新成对应的索引值。具体过程如下图:

如果是已经出现过的,例如上述示例中的 abcabc,当第二次遇到a时,我们就更新left成为第一个b所在的位置,此时惊奇的发现left要移动的位置恰好就是map.get(’a‘) + 1=1,我们将'a'用序列来表示,放在一起就是map.get(s.charAt(i)) + 1。其他情况可以参考图示依次类推。
有一种特殊情况我们需要考虑,例如abba,我们第二次访问b时,left=map.get(’b‘) + 1=2。
然后继续访问第二个a,此时left=map.get(’a‘) + 1=1,也就是left后退了,显然不对。
我们应该让left在2的基础上继续向前,那该怎么办呢?和原来的对比一下,将最大的加1就可以了,也就是:
left = Math.max(left,map.get(s.charAt(i)) + 1);
完整的代码如下:

public  int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max = 0;
        int left = 0;
        for (int right = 0; right < s.length(); right++) {
            if (map.containsKey(s.charAt(right))) {
                left = Math.max(left, map.get(s.charAt(right)) + 1);
            }
            map.put(s.charAt(right), right);
            max = Math.max(max, right - left + 1);
        }
        return max;
}

除了上述方法,不用Hash存储索引,也可以用滑动窗口思想来解决,感兴趣的可以研究一下。

1.2 至多包含两个不同字符的最长子串?

给定一个字符串 s ,找出 至多 包含两个不同字符的最长子串 t ,并返回该子串的长度,这就是LeetCode159题。例如:

输入: "eceba"

输出: 3

解释: t 是 "ece",长度为3。

我们仍然使用left和right来锁定一个窗口,然后一边向右移动一边分析。我们用一个序列来看一下:aabbcccd。

?

我们接下来需要解决两个问题,一个是怎么判断只有2个元素,另一个是移除的时候怎么知道移除谁,以及移除之后left是什么。
要判断只有2个元素,还是Hash好用,每一个时刻,这个 hashmap 包括不超过 3 个元素。这里还要考虑到要移除谁,所以我们要设计一下Hash的Key-Value的含义。我们把字符串里的字符都当做键,在窗口中的最右边的字符位置作为值。此时使用下面的代码就可以确定要删除谁,以及窗口left的新位置:

伪码,从Hash中找最小值

del_idx = Collections.min(hashmap.values());

left = del_idx + 1;

为什么呢?我们还是画图看一下:

所以我们可以充分利用Map的工具来解决该问题:

public  int lengthOfLongestSubstringTwoDistinct(String s) {

        if (s.length() < 3) {
            return s.length();
        }
        int left = 0, right = 0;
        HashMap<Character, Integer> hashmap = new HashMap<>();
        int maxLen = 2;

        while (right < s.length()) {

            if (hashmap.size() < 3)
                hashmap.put(s.charAt(right), right++);

            // 如果大小达到了3个
            if (hashmap.size() == 3) {
                // 最左侧要删除的位置
                int del_idx = Collections.min(hashmap.values());
                hashmap.remove(s.charAt(del_idx));
                // 窗口left的新位置
                left = del_idx + 1;
            }

            maxLen = Math.max(maxLen, right - left);
        }
        return maxLen;
    }

1.3 至多包含 K 个不同字符的最长子串

如果再提高一下难度, 至多包含 K 个不同字符的最长子串该怎么办呢?这就是LeetCode340题。
题目的完整要求是:给定一个字符串 s,找出 至多 包含 k 个不同字符的最长子串T。示例:

输入: s = "eceba", k = 2

输出: 3

解释: 则 T 为 "ece",所以长度为 3。

本题与上面的题几乎没有区别,只要将判断hash大小为2改成k就可以,超过2就是k+1。十分钟实现:

public  int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s.length() < k + 1) {
            return s.length();
        }
        int left = 0, right = 0;
        HashMap<Character, Integer> hashmap = new HashMap<>();
        int maxLen = k;
        while (right < s.length()) {
            if (hashmap.size() < k + 1)
                hashmap.put(s.charAt(right), right++);
            // 如果大小达到了k个
            if (hashmap.size() == k + 1) {
                int del_idx = Collections.min(hashmap.values());
                hashmap.remove(s.charAt(del_idx));
                // 窗口left的新位置
                left = del_idx + 1;
            }
            maxLen = Math.max(maxLen, right - left);
        }
        return maxLen;
    }

2 长度最小的子数组?

LeetCode209.长度最小的子数组,给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。

输入:target = 7, nums = [2,3,1,2,4,3]

输出:2

解释:子数组 [4,3] 是该条件下的长度最小的子数组。

?本题可以使用双指针来解决,也可以视为队列法,基本思路是先让元素不断入队,当入队元素和等于target时就记录一下此时队列的容量,如果队列元素之和大于target则开始出队, 直到小于target则再入队。
如果出现等于target的情况,则记录一下此时队列的大小,之后继续先入队再出队。每当出现元素之和等于target时我们就保留容量最小的那个。
实现代码如下:

public int minSubArrayLen(int target, int[] nums) {
        int left = 0, right = 0, sum = 0, min = Integer.MAX_VALUE;
        while (right < nums.length) {
            sum += nums[right++];
            while (sum >= target) {
                min = Math.min(min, right - left);
                sum -= nums[left++];
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }

3. 盛水最多的容器?

LeetCode11.给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。

示例:

输入:[1,8,6,2,5,4,8,3,7]

输出:49

解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

本题看似复杂,但其实简单的很。设两指针 i , j ,指向的水槽板高度分别为 h[i] , h[j] ,此状态下水槽面积为S(i,j) 。由于可容纳水的高度由两板中的 短板 决定,因此可得如下面积公式 :
S(i,j)=min(h[i],h[j])×(j?i)
在每个状态下,无论长板或短板向中间收窄一格,都会导致水槽底边宽度?1 变短:

  • 若向内移动短板 ,水槽的短板min(h[i],h[j]) 可能变大,因此下个水槽的面积可能增大 。
  • 若向内移动长板 ,水槽的短板min(h[i],h[j]) 不变或变小,因此下个水槽的面积一定变小 。

因此,只要初始化双指针分列水槽左右两端,循环每轮将短板向内移动一格,并更新面积最大值,直到两指针相遇时跳出;即可获得最大面积。?

public int maxArea(int[] height) {
    int i = 0, j = height.length - 1, res = 0;
    while(i < j) {
        res = height[i] < height[j] ? 
              Math.max(res, (j - i) * height[i++]): 
              Math.max(res, (j - i) * height[j--]); 
    }
    return res;
}

4 寻找子串异位词(排列)?

如果两个字符串仅仅是字母出现的位置不一样,则称两者相互为对方的一个排列,也称为异位词。
如果判断两个字符串是否互为排列,是字符串的一个基本算法。现在我们给增加难度。看LeetCode567和438两个题。

4.1 字符串的排列

LeetCode567.给你两个字符串s1和s2 ,写一个函数来判断 s2是否包含 s1的排列。如果是,返回 true ;否则,返回 false 。换句话说,s1 的排列之一是 s2 的子串 。其中s1和s2都只包含小写字母。

示例:

输入:s1 = "ab" s2 = "eidbaooo"

输出:true

解释:s2 包含 s1 的排列之一 ("ba").

本题因为字符串s1的异位词长度一定是和s2字符串的长度一样的,所以很自然的想到可以以s1.length()为大小截图一个固定窗口,然后窗口一边向右移动,一边比较就行了。此时可以将窗口内的元素和s1先做一个排序,然后再比较即可,但是这样做的问题是排序代价太高了,我们需要考虑性能更优的方法。
所谓的异位词不过两点:字母类型一样,每个字母出现的个数也是一样的。题目说s1和s2都仅限小写字母,因此我们可以创建一个大小为26的数组,每个位置就存储从a到z的个数,为了方便操作,索引我们使用
index=s1.charAt(i) - 'a'
来表示,这是处理字符串的常用技巧。
此时窗口的right向右移动就是执行:
charArray2[s2.charAt(right) - 'a']++;
而left向右移动就是执行:

伪码:

int left = right - sLen1;

charArray2[s2.charAt(left) - 'a']--;

所以,完整代码如下:

public boolean checkInclusion(String s1, String s2) {
    int sLen1 = s1.length(), sLen2 = s2.length();
    if (sLen1 > sLen2) {
        return false;
    }
    int[] charArray1 = new int[26];
    int[] charArray2 = new int[26];
    for(int i=0;i<sLen1;i++){
        ++charArray1[s1.charAt[i]-'a'];
        ++charArray2[s2.charAt[i]-'a'];
    }
    if (Arrays.equals(charArray1, charArray2)) {
            return true;
    }
    for(int right=sLen1;right<sLen2;right++){
        charArray2[s2.charAt(right)-'a']++;
        int left=right-sLen2;
        charArray2[s2.charAt(left)-'a']--;
        if (Arrays.equals(charArray1, charArray2)) {
                return true;
        }
    }
    return false;
}

?上面只是判断有没有,那如果让你确定一下有几个呢?有或者如果有的话,将异位词的开始位置输出出来怎么做呢?这就是LeetCode438题。

4.2 找到字符串中所有字母异位

LeetCode438.找到字符串中所有字母异位词,给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。注意s和p仅包含小写字母。
异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。例如:

输入: s = "cbaebabacd", p = "abc"

输出: [0,6]

解释:

起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。

起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

本题的思路和实现与上面几乎一模一样,唯一不同的是需要用一个List,如果出现异位词,还要记录其开始位置,那直接将其add到list中就可以了。完整代码:

public List<Integer> findAnagrams(String s, String p) {
       int sLen = s.length(), pLen = p.length();
        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }
        List<Integer> ans = new ArrayList<Integer>();
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        //先分别初始化两个数组
        for (int i = 0; i < pLen; i++) {
            sCount[s.charAt(i) - 'a']++;
            pCount[p.charAt(i) - 'a']++;
        }
        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }

        for (int left = 0; left < sLen - pLen; left++) {
            sCount[s.charAt(left) - 'a']--;
            int right=left + pLen;
            sCount[s.charAt(right) - 'a']++;

            if (Arrays.equals(sCount, pCount)) {
            //上面left多减了一次,所以
                ans.add(left + 1);
            }
        }
        return ans;
}

?

?

文章来源:https://blog.csdn.net/m0_53401014/article/details/134876765
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。