滑动窗口技术

ゝ一纸荒年。 2022-02-01 14:19 289阅读 0赞

leetcode3.209等题目都是滑动窗口解决的。  
都是一种在数组这种数据结构中寻找最长，最短的情况，咋一看刚开始想着动态规划可能是这种题目的解法。  
但是适用于动态规划的题目的解法不适用于这种类型的题。毕竟动态规划解决的是含有1.最优子结构性质。2.重叠子问题。3.无后效性等情况。  
但是这都是在数组中**有多个可行解**，都是在**满足一定条件下把当前的不确定的结果（可能是最大或者最小的情况给保存下来）**,不断去寻找，直到其中左指针到达数组的末尾，结束寻找。

**写代码之前的特殊情况的考虑真的重要**。考虑越清晰，越好写。  
附上错误代码,**leetcode438题目**

public List<Integer> findAnagrams(String s, String p) {
            List<Integer> list = new ArrayList<>();
            if (s == null)
                return list;
            //Map<Character, Integer> map = new HashMap<>();
            int[] number = new int[26];
            char[] chars = p.toCharArray();
            char[] nums = s.toCharArray();
            int len = chars.length;
            for (int i = 0; i < len; i++) {
                //  map.put(chars[i],0);
            }
            int l = 0, r = -1;
            int charlen = p.length();
            return null;
        }
    /*
            //滑动
            while(l < nums.length){
    
                if(r+1 < nums.length && forMap(map) < charlen){
                    //移动r++
                    if(map.containsKey(nums[++r])){
                        //包含，就正常操作
                       if(map.get(nums[r]) != 1) {
                           map.put(nums[r], 1);
                        }else{
    
                            l++;
    
                        }
                    }else{
                        //不包含，非正常操作就好了
                        //l都置下一位，r置当前不符合的位置
                        l = r + 1;
                        //同时清空map中所有的值
                        clear(map);
                    }
    
                }else{
                    //对左指针l--,从map去掉l对应的1
                    if(map.containsKey(nums[l]))
                        map.put(nums[l],0);
                    //都要l++;
                    l++;
                }
    
                if(forMap(map) == charlen){
                   list.add(l);
                }
            }
    
            return list;
        }
    
        public int forMap(Map<Character,Integer> map){
    
            int sum = 0;
            for(Integer a:map.values()){
                sum += a;
            }
            return sum;
        }
    
        public void clear(Map<Character,Integer> map){
    
           for(Map.Entry<Character,Integer> entry:map.entrySet()){
               map.put(entry.getKey(),0);
           }
    
        }
    
     */

感觉自己陷入了一种误区，误区在哪呢？**在不懂滑动窗口的本质**。应该去思考这个本质

*  1.什么情况下右移
 *  2.什么情况下左移
 *  3.满足条件下应该做什么操作。

这3者又都是根据不同的题目做出不同的要求。根据实际情况的变化而变化。  
其次在438题目中，**我很操蛋的去维护一个Map,其实这里根据题目情况只有26个字符，根本不用用map，所以得到一个感受就是能尽量简单的数据结构解决的问题，尽量不要用复杂的数据结构，复杂的数据结构操作起来也花时间，**  
大神用数组来保存下来，**用 res\[chars\[i\]-‘a’\] += 1; 每一个字符减去’a’即可，这是小技巧，求自己记住了。** 之前的思路类似，就是当前符合就操作Map，维护这个map，为啥不用2个数组呢？ s字符串用一个，p字符串也用一个，用s数组去不断判断p数组，满足与否。

leetcode438题  
1.什么情况下右移，即每次不管找到与否，都右移，并且加入s数组中。  
2.啥时候左移呢？ 即当r-l+1>p.length()这个条件，就进行s数组 s\[chars\[l++\]-‘a’\]–;减去1同时l++,这样设立的条件，特别符合题目给出的情况下，符合所有的不满足情况，都进行滑动窗口的左边界移动。  
3.当题目满足就将list.add即可。

正确的大神思路：

class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            
            List<Integer> res = new ArrayList<>();
            
            if(s.length() < p.length())
                return res;
            
            char[] charp = p.toCharArray();
            char[] chars = s.toCharArray();
            int[] res_p = new int[26];
            
            for(char c:charp)
                res_p[c-'a'] += 1; 
            
            int[] res_s = new int[26];
            int l = 0,r = -1;
            while(r+1<s.length()){
    
                r++;
                
                res_s[chars[r]-'a'] ++;
                
                if(r-l+1>p.length())
                    res_s[chars[l++]-'a']--;
                
                if(r-l+1 == p.length() && same(res_s,res_p))
                    res.add(l);
                
            }
            
            return res;
        }
        
        public boolean same(int[] res_s,int[] res_p){
            
                for(int i=0;i<26;i++){
                    
                    if(res_s[i]!=res_p[i])
                        return false;
                    
                }
                return true;
        }
    }

发散一下：即如果当前数组中，寻找同位数组p在s中。同样也能用这个思路。