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

【算法】——滑动窗口专题

article 2024/11/6 12:00:32

阿华代码，不是逆风，就是我疯

你们的点赞收藏是我前进最大的动力！！

希望本文内容能够帮助到你！！

一：长度最小的子数组

二：无重复字符的最长子串

三：最大连续1的个数

四：将x减到0的最小操作数

五：水果成篮

六：找到字符串中所有字母的异位词

七：串联所有单词的子串

八：最小覆盖子串

一：长度最小的子数组

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0 , right = 0 , sum = 0 , n = nums.length;
        int len = Integer.MAX_VALUE;
        
        for(;right < n ; right++){
            //进入窗口
            sum += nums[right];
            while(sum >= target){
                //更新值
                len = Math.min(len,right - left + 1);
                //出窗口
                sum -= nums[left];
                left++;
            }
        }
        return len == Integer.MAX_VALUE ? 0 : len; 
        
        


    }
}

二：无重复字符的最长子串

3. 无重复字符的最长子串 - 力扣（LeetCode）

class Solution {
    public int lengthOfLongestSubstring(String ss) {
        int left = 0 , right = 0 , ret = 0;
        char[] s = ss.toCharArray();
        int n = s.length;
        int[] hash = new int[128];
        while(right < n){
            hash[s[right]]++;
            while(hash[s[right]] > 1){
                hash[s[left++]]--;//出窗口
            }
            ret = Math.max(ret , right - left + 1);
            right++;
        }
        return ret;

    }
}

三：最大连续1的个数

class Solution {
    public int longestOnes(int[] nums, int k) {
        int left = 0 , right = 0 , count = 0;
        int n = nums.length , ret = 0;
        while(right < n){
            if(nums[right] == 1){
                right++;
            }else{
                count++;
                right++;
            }
            while(count > k){
                if(nums[left] == 1){
                    left++;
                }else{
                    count--;
                    left++;
                }
                
            }
            

            ret = Math.max(ret,right-left);

        } 
        return ret;

    }
}

四：将x减到0的最小操作数

1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）

class Solution4 {
    public int minOperations(int[] nums, int x) {
        int left = 0 , right = 0 , count = 0 ,sum = 0;
        int n = nums.length;
        for(int i = 0 ; i < n ; i++){
            sum += nums[i];
        }
        int target = sum - x , tem = 0;
        if(target < 0){
            return -1;
        }
        if(target == 0){
            return n;
        }
        for(; right < n ; right++){
            //进窗口不判断
            tem += nums[right];
            while(tem > target ){
                tem -= nums[left];
                left++;
            }//执行顺序也有讲究，最后一步判断
            if(tem == target){
                count = Math.max(count , right-left+1);
            }
        }
        if(count == 0){
            return -1;
        }
        return n-count;
    }
}

五：水果成篮

904. 水果成篮 - 力扣（LeetCode）

class Solution {
    public int totalFruit(int[] f) {
        Map<Integer,Integer> hash = new HashMap<Integer,Integer>();
        int ret = 0;
        for(int left = 0 , right = 0 ; right < f.length ; right++){
            //进窗口
            int in = f[right];
            hash.put(in,hash.getOrDefault(in,0)+1);
            while(hash.size() > 2){//判断
                //出窗口
                int out = f[left];
                hash.put(out,hash.get(out)-1);
                if(hash.get(out) == 0){
                    hash.remove(out);
                }
                left++;
            }
            ret = Math.max(ret,right - left + 1);
        }
        return ret;
    }
}

六：找到字符串中所有字母的异位词

438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

class Solution {
    public List<Integer> findAnagrams(String ss, String pp) {
        List<Integer> list = new ArrayList<Integer>();
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        int[] hashS = new int[26];
        int[] hashP = new int[26];

        for(char x : p){
            hashP[ x - 'a']++;
        }  

        for(int right = 0 , left = 0 , count = 0 ; right < ss.length() ; right++ ){
            char in = s[right];
            hashS[ in - 'a']++;
            if(hashS[in - 'a'] <= hashP[in - 'a']){
                count++;//进入的是有效字符
            }
            char out = s[left];
            if(right - left + 1 > pp.length()){
                hashS[out - 'a']--;
                if(hashS[out - 'a'] < hashP[out - 'a']){
                    count--;
                }
                left++;
            }
            if(count == pp.length()){
                list.add(left);
            }
        }
        return list;
        
    }
}

七：串联所有单词的子串

30. 串联所有单词的子串 - 力扣（LeetCode）

    class Solution8 {
        public List<Integer> findSubstring(String s, String[] words) {
            List<Integer> ret = new ArrayList<Integer>();
            //先把words中的元素放到HashMap中//每个元素的长度为m，数组长度为n,记录元素种类ele
            Map<String,Integer> hash1 = new HashMap<String,Integer>();
            int m = words[0].length() , n = words.length ,ele = 0;
            for(String ss : words){
                hash1.put(ss,hash1.getOrDefault(ss,0)+1);

            }



            for(int i = 0 ; i < m ; i++ ){
                //wc太绝了hashMap每次i移动时需要初始化一下，要不然上一次的值还存留在HashMap中
                Map<String,Integer> hash2 = new HashMap<String,Integer>();
                for(int left = i , right = i , count = 0 ; right + m <= s.length()  ; right += m){
                    //进窗口
                    String in = s.substring(right,right+m);
                    hash2.put(in,hash2.getOrDefault(in,0)+1);
                    //判断count加不加
                    if(hash2.get(in) <= hash1.getOrDefault(in,0)){
                        count++;
                    }
                    //出窗口
                    while(right - left + 1 > m * n ){
                        String out = s.substring(left,left+m);
                        left+=m;
                        if(hash2.get(out) <= hash1.getOrDefault(out,0)){
                            count--;
                        }
                        hash2.put(out,hash2.get(out)-1);
                    }
                    if(count == n){
                        ret.add(left);
                    }


                }
            }
            return ret;

        }
    }

八：最小覆盖子串

76. 最小覆盖子串 - 力扣（LeetCode）

class Solution {
    public String minWindow(String ss, String tt) {
       //先把要找的字符tt转化为数组并放到哈希表里
       char[] t = tt.toCharArray();
       int[] hash1 = new int[128];
       int kind = 0;//统计tt字符串中有多少种字符
       for(char ch : t){
            hash1[ch]++;
            if(hash1[ch] == 1){
                kind++;
            }
       }

       //同样把字符ss转化为数组
       char[] s = ss.toCharArray();
       int[] hash2 = new int[128];
       int len = Integer.MAX_VALUE;
       int left = 0 , right = 0 , begin = -1 ;
       
       for(int count = 0; right < s.length ; right++){
             //进窗口
            char in = s[right];
            hash2[in]++;
            //判断如果直接判断两个哈希表非常耗费时间引入count
            if(hash1[in] == hash2[in]){
                count++;
            }

            
            //更新结果(如果种类一直相同，那就一直出窗口所以用while)
            while(count == kind){
                if(right - left + 1 < len){
                    begin = left;
                    len = right-left+1;
                }

                //出窗口
                char out = s[left++];
                if(hash2[out] == hash1[out] ){//考虑两种情况，出的是有效字符还是无效字符
                    count--;
                }
                hash2[out]--;  
                
            }
            
       }
            //for循环走完了一直进不去while循环，返回空字符串
            if(len == Integer.MAX_VALUE){
                    return new String();
            }else{
                String ret = ss.substring(begin,begin+len);
                return ret;
            }
       
        
    }
}

查看全文

http://www.kler.cn/a/381513.html