滑动窗口Sliding Window Algorithm

2021-03-06 19:26

阅读：792

标签：let input 嵌套循环元素 ref nbsp string i++ 滑动

应用及优点：

1.可用于解决数组或者字符串的子元素问题。

2.用单循环代替了嵌套循环问题，时间复杂度低。

3.用双指针维护动态窗口。

Longest Substring Without Repeating Characters无重复最长子串

Find All Anagrams in a String（找到字符串中所有字母异位词）

Minimum Window Substring最小覆盖子串

209. Minimum Size Subarray Sum长度最小子数组

以“Find All Anagrams in a String”为例：

Given a string s and a non-empty string p, find all the start indices of p‘s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

class Solution {
    public List findAnagrams(String s, String p) {
        int [] need=new int[128];
        int [] win=new int[128];
        int left=0;int right=0;
        List res=new ArrayList();
        for(int i=0;i){
            need[p.charAt(i)]++;//将目标数组中各元素计数。
        }
        while(rights.length()){
            win[s.charAt(right)]++;//窗口右移
            while(rightneed[s.charAt(right)]){//窗口停止右移条件
                win[s.charAt(left)]--;
                left+；//窗口左移
            }
            if(right-left+1==p.length()){
                res.add(left);
            }
            right++;

        }
        return res;
    }
}

滑动窗口Sliding Window Algorithm

标签：let input 嵌套循环元素 ref nbsp string i++ 滑动

原文地址：https://www.cnblogs.com/NeverGiveUp0/p/12850775.html

上一篇：win10系统wifi能连上但不能上网怎么办[系统天地]

下一篇：高德地图实现标点、点聚合和信息窗体

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：滑动窗口Sliding Window Algorithm
文章链接：http://soscw.com/essay/60991.html

亲，登录后才可以留言！

滑动窗口Sliding Window Algorithm

Longest Substring Without Repeating Characters无重复最长子串

Find All Anagrams in a String（找到字符串中所有字母异位词）

Minimum Window Substring最小覆盖子串

209. Minimum Size Subarray Sum长度最小子数组

评论

热门文章

推荐文章

最新文章

置顶文章