算法练习03——滑动窗口

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

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

class Solution {
    
    public int lengthOfLongestSubstring(String s) {
    
        //哈希表＋滑动窗口
        int res=0;
        int left=-1;
        Map<Character,Integer> hash=new HashMap<>();
        for(int right=0;right<s.length();right++){
    
            if(hash.containsKey(s.charAt(right))){
    
                left=Math.max(left,hash.get(s.charAt(right)));
            }
            hash.put(s.charAt(right),right);
            res=Math.max(res,right-left);
        }
        return res;
    }
}

438. 找到字符串中所有字母异位词*

https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?envType=study-plan-v2&envId=top-100-liked

class Solution {
    
    public List<Integer> findAnagrams(String s, String p) {
    
        List<Integer> res=new ArrayList<>();
        int sLen=s.length();
        int pLen=p.length();

        if(sLen<pLen){
    
            return res;
        }
        //建立两个数组存放字符串中字母出现的词频，并以此作为标准比较
        int [] scount=new int[26];
        int [] pcount=new int[26];

        //当滑动窗口的首位在s[0]处时 （相当于放置滑动窗口进入数组）
        for(int i=0;i<pLen;i++){
    
            ++scount[s.charAt(i)-'a']; //记录s中前pLen个字母的词频
            ++pcount[p.charAt(i)-'a']; //记录要寻找的字符串中每个字母的词频(只用进行一次来确定)
        }

        //判断放置处是否有异位词 (在放置时只需判断一次)
        if(Arrays.equals(scount,pcount)){
    
            res.add(0);
        }   

        //开始让窗口进行滑动
        for(int i=0;i<sLen-pLen;i++){
     //i是滑动前的首位
            --scount[s.charAt(i) -'a'];       //将滑动前首位的词频删去
            ++scount[s.charAt(i+pLen) -'a'];  //增加滑动后最后一位的词频（以此达到滑动的效果）

            //判断滑动后处，是否有异位词
            if(Arrays.equals(scount,pcount)){
    
                res.add(i+1);
            } 
        }
        return res;
    }
}

30. 串联所有单词的子串***(hard)

https://leetcode.cn/problems/substring-with-concatenation-of-all-words/

class Solution {
    
    public List<Integer> findSubstring(String s, String[] words) {
    
        List<Integer> res = new ArrayList<>();
        // 所有单词的个数
        int num = words.length;
        // 每个单词的长度（是相同的）
        int wordLen = words[0].length();
        // 字符串长度
        int stringLen = s.length();

        for (int i = 0; i < wordLen; i++) {
    
            // 遍历的长度超过了整个字符串的长度，退出循环
            if (i + num * wordLen > stringLen) {
    
                break;
            }
            // differ表示窗口中的单词频次和words中的单词频次之差
            Map<String, Integer> differ = new HashMap<>();
            // 初始化窗口，窗口长度为num * wordLen,依次计算窗口里每个切分的单词的频次
            for (int j = 0; j < num; j++) {
    
                String word = s.substring(i + j * wordLen, i + (j + 1) * wordLen);
                differ.put(word, differ.getOrDefault(word, 0) + 1);
            }
            // 遍历words中的word，对窗口里每个单词计算差值
            for (String word : words) {
    
                differ.put(word, differ.getOrDefault(word, 0) - 1);
                // 差值为0时，移除掉这个word
                if (differ.get(word) == 0) {
    
                    differ.remove(word);
                }
            }
            // 开始滑动窗口
            for (int start = i; start < stringLen - num * wordLen + 1; start += wordLen) {
    
                if (start != i) {
    
                    // 右边的单词滑进来
                    String word = s.substring(start + (num - 1) * wordLen, start + num * wordLen);
                    differ.put(word, differ.getOrDefault(word, 0) + 1);
                    if (differ.get(word) == 0) {
    
                        differ.remove(word);
                    }
                    // 左边的单词滑出去
                    word = s.substring(start - wordLen, start);
                    differ.put(word, differ.getOrDefault(word, 0) - 1);
                    if (differ.get(word) == 0) {
    
                        differ.remove(word);
                    }
                    word = s.substring(start - wordLen, start);
                }
                // 窗口匹配的单词数等于words中对应的单词数
                if (differ.isEmpty()) {
    
                    res.add(start);
                }
            }
        }
        return res;
    }
}

209. 长度最小的子数组

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

class Solution {
    
    public int minSubArrayLen(int target, int[] nums) {
    
        int len=nums.length;
        int res=Integer.MAX_VALUE;
        int temp=0;
        int start=0;
        int sum=0;
        for(int i=0;i<len;i++){
    
            sum+=nums[i];
            while(sum>=target){
    
                temp=i-start+1;
                res=Math.min(res,temp);
                sum-=nums[start];
                start++;
            }
        }
        return res==Integer.MAX_VALUE ? 0:res;
    }
}