Java滑動窗口算法題目練習(附詳細圖文及代碼)

更新時間：2025年10月19日 11:01:42 作者：代碼不停

在數(shù)據(jù)處理和算法中,滑動窗口是一種常見的技術(shù),用于解決一些數(shù)組或字符串相關(guān)的問題,這篇文章主要介紹了Java滑動窗口算法題目練習的相關(guān)資料,文中通過代碼介紹的非常詳細,需要的朋友可以參考下

長度最小的子數(shù)組

題目解析：這里給我們一個全是正整數(shù)的數(shù)組和一個目標值，讓我們找一段連續(xù)的區(qū)間，這個區(qū)間的值之和是大于等于目標值的，從這個數(shù)組中找到一個最小的區(qū)間長度，如果不存在的話就返回0
算法原理：1.首先我們是可以使用暴力解法，雙重for循環(huán)進行遍歷出所有的情況，當滿足區(qū)間的值大于等于目標值的話就進行結(jié)果更新，反之繼續(xù)向后操作，我們可以發(fā)現(xiàn)這里是有許多的是多余的，就像如果此時的這個區(qū)間的值已經(jīng)大于這個目標值了，如果繼續(xù)向后操作的話，這個數(shù)組是正整數(shù)數(shù)組，肯定還是大于等于目標值，但是長度變長了，我們要找到是最短的，因此我們可以不需要讓其重復操作，直接開始下一次循環(huán)就行
2."同向雙指針"也叫滑動窗口算法，這里我們可以使用left和right兩個指針向同一個方向移動，并且不回退，此時的思想就和上面暴力解法優(yōu)化思想一樣，一直進行將right下標對應的值放入sum變量中，當sum>=target時候就可以將minlen更新了，此時不必將right向后移動了，只需要將left下標的值減去，讓left向后移動，這樣重復操作進行查找，直到right遍歷完整個數(shù)組就完成了

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int sum = 0;
        int len = Integer.MAX_VALUE;//剛開始定義長度是int可以表示最大整數(shù)
        int n = nums.length;
        for(int left = 0,right = 0; right < n;right++){
            sum += nums[right];//入窗口
            //結(jié)果判斷
            while(sum >= target){
                len = Math.min(len , right - left + 1);//結(jié)果更新
                sum -= nums[left++]; //出窗口
            }
        }
        return len == Integer.MAX_VALUE ? 0 : len;
    }
}

時間復雜度：O(N),空間復雜度：O(1)

無重復字符的最長子串

題目解析：這里就是給了我們一個字符串s,讓我們在里面找出最長連續(xù)不重復的子串長度，如果是空字符串就返回0
算法原理：1.暴力解法+哈希表(判斷字符是否重復出現(xiàn))，就是將其字符串中所有情況全部遍歷一遍，將其存放在哈希表中，遍歷的過程中判斷是否已經(jīng)存放在哈希表中，如果存在這時候就更新結(jié)果，并就跳出內(nèi)循環(huán)，就這樣一直重復操作
2.滑動窗口+哈希表，上面的暴力解法中會出現(xiàn)一些多余的操作，這里我們用left和right這兩個同向雙指針，不回退，right用來遍歷整個字符串并將其放入哈希表中，并當right下標的字符存放后發(fā)現(xiàn)其如果沒重復就更新結(jié)果 ，如果存在重復，那肯定是此下標有重復的，這時候就將left對應的字符從哈希表中刪除，但我們可能要刪除很多次，因為我們并不知道其那個是重復的，所以此時是個循環(huán)，直到?jīng)]有重復為止繼續(xù)更新結(jié)果，就這樣一直right放入窗口，判斷是否有重復字符，有的話就一直出left到?jīng)]有重復字符為止，更新結(jié)果，就這樣一直到right遍歷完整個字符串

我們這里是使用int類型的數(shù)組來模擬哈希表，因為字符對應的是ASCLL碼值

因此我們可以根據(jù)每次存放將其下標的值++，大于1說明有重復的就進行出窗口

class Solution {
    public int lengthOfLongestSubstring(String ss) {
        int[] hash = new int[128];//這里使用數(shù)組來表示其hash，如果其對應的位置>1說明有重復的
        int len = 0;
        char[] s = ss.toCharArray();//將其字符串轉(zhuǎn)換成字符數(shù)組，方便后面使用
        //使用同向雙指針，滑動窗口
        for(int left = 0,right = 0;right < s.length;right++){
            //入窗口
            hash[s[right]]++;//字符對應的ASCLL碼值作為下標++
            //判斷，如果>1，說明有重復的了，就要出窗口
            while(hash[s[right]] > 1){
                //出窗口
                hash[s[left++]]--;
            }
            //更新結(jié)果
            len = Math.max(len,right - left+1);
        }
        return len;
    }
}

最大連續(xù)1的個數(shù)|||

題目解析：題目就是找到最大連續(xù)1的個數(shù)，并且最多可以反轉(zhuǎn)k個0
因此我們可以將其題目轉(zhuǎn)換成找出一個最長子數(shù)組并且里面0的個數(shù)步超過k個
算法原理：1.暴力枚舉+count(記錄當前區(qū)間0的個數(shù))
2.滑動窗口+count(記錄當前區(qū)間0的個數(shù))

class Solution {
    public int longestOnes(int[] nums, int k) {
        int len = 0;
        int n = nums.length;
        int count = 0;//用于統(tǒng)計當前區(qū)間0的個數(shù)
        for(int left = 0,right = 0;right < n;right++){
            //記錄當前0的個數(shù)
            if(nums[right] == 0){
                count++;
            }
            //出窗口
            while(count > k){
                if(nums[left++] == 0){
                    count--;
                }
            }
            //更新結(jié)果
            len = Math.max(len , right - left + 1);
        }
        return len;
    }
}

時間復雜度：O(N)，空間復雜度：O(1)

將x減到0的最小操作數(shù)

題目解析：就是給了我們一個目標值x讓我們每次從nums數(shù)組最左邊或者最右邊找一個數(shù)，將其減去，減去就要從數(shù)組中移除這個數(shù)，就這樣一直重復操作，找出一個最小操作數(shù)，我們可以發(fā)現(xiàn)這個問題十分繁瑣，因為我們每次也不直到是從左邊還是右邊
因此我們可以正難則反 我們可以將題目轉(zhuǎn)換為在這個數(shù)組連續(xù)區(qū)間找一個最長的長度和為整個數(shù)組的和 - x，最后返回數(shù)組長度 - 找到的長度就行
算法原理：首先算出總的數(shù)組和sum ,我們的目標值target = sum - x，我們直接從數(shù)組中找出一個最長長度區(qū)間，使其值等于target
這里找到target目標值是采用滑動窗口即同向雙指針，我們使用left和right兩個指針，right遍歷整個數(shù)組，total記錄當前區(qū)間的值，
當 total == target時候就更新結(jié)果
當total > target就出窗口，刪除left下標的值，并讓left++，直到total <= target為止
反之就是小于，就一直將right下標的值入窗口

class Solution {
    public int minOperations(int[] nums, int x) {
        //這里采用正難則反的思想，我們是每次從最右邊和最左邊找數(shù)相加，看何時等于x
        //我們可以轉(zhuǎn)換為在這個數(shù)組連續(xù)區(qū)間找一個最長的長度和為 整個數(shù)組的和 - x
        int sum = 0;//nums整個數(shù)組的和
        int n = nums.length;
        for(int i = 0; i < n;i++){
            sum += nums[i];
        }
        //此時我們的目標值變成sum - x
        int target = sum - x;
        //如果全部sum和都<x說明找不到
        if(target < 0){
            return -1;
        }
        int total = 0;
        int len = -1;
        //后面就使用滑動窗口來找最長子串使其長度等于target目標值
        for(int left = 0,right = 0;right < n;right++){
            //入窗口
            total += nums[right];
            //判斷
            while(total > target){
                total -= nums[left++];//出窗口
            }
            //等于的時候才更新結(jié)果
            if(total == target){
               len =  Math.max(len,right - left + 1);
            }
        }
        return len == -1 ? -1 : n - len;
    }
}

水果成藍

題目解析：就是給我們一個fruits數(shù)組，里面又好多種類，讓我們用兩個籃子放水果，并且每個籃子只能放一種水果，并且不可以跳著摘水果，遇到第三種水果直接停止采摘，獲取其中最多摘多少水果
問題可以轉(zhuǎn)換為：找出一個最長的子數(shù)組，并且里面不超過兩種水果
算法原理：暴力解法+hash，可以使用雙重for循環(huán)進行遍歷，left和right這兩個變量，但是其中有一些多余的操作，例如當水果的種類大于2時，我們此時采用的是，讓left++,right回到left的位置繼續(xù)進行遍歷，但是我們可以發(fā)現(xiàn)，原本[left,right]這個區(qū)間種類>2，讓其回去，此時讓left++,其中的中類要么不變，要么減小，肯定不會增加
滑動窗口+hash
先不斷的將right下標放入hash中
當種類>2的時候就要出窗口left下標對應的水果數(shù)量–，當其是0的時候說明其種類減少，將其從hash中刪除，left++
更新結(jié)果
len = Math.max(len,right - left+1)

class Solution {
    public int totalFruit(int[] fruits) {
        //此時我們使用一個數(shù)組來實現(xiàn)hash
        int n = fruits.length;
        int[] hash = new int[n+1];
        int len = 0;//最長的長度
        for(int left = 0,right = 0,kinds = 0;right < n ;right++){
            //入窗口
            if(hash[fruits[right]] == 0){
                kinds++;//如果這個窗口沒有添加過這個元素，此時種類增多
            }
            hash[fruits[right]]++;
            //當kinds>2進行出窗口
            while(kinds > 2){
                //出窗口
                hash[fruits[left]]--;
                //此時如果這個連續(xù)的區(qū)間沒有了這個元素，此時的種類就減小
                if(hash[fruits[left]] ==0){
                    kinds--;
                }
                left++;
            }
            //更新結(jié)果
            len = Math.max(len,right - left + 1);
        }
        return len;
    }
}

時間復雜度：O(N)
空間復雜度：O(N)

找到字符串中所有字母異位詞

字母異位詞是通過重新排列不同單詞或短語的字母而形成的單詞或短語，并使用所有原字母一次。

題目解析：就是給我們s和p兩個字符串，讓我們再s中找到所有p的異位詞子串，并將其索引，最后返回其中所有的索引
算法原理：首先我們想到的是暴力解法+hash，一直遍歷s串中所有和p長度相同的子串，并且要同過hash比較其中是否相同，相同就將其下標放入一個集合中，但是仍有一些多余的部分
滑動窗口+hash：left = 0,right = 0
使用left和right來確定窗口，并且此時的窗口長度是一定的，不斷讓right向后走，left也想后走，right并不需要回頭，因為我們要進入下一個窗口僅需將left下標對應的字符出hash，將right+1下標入hash就行,此時就進入下一個窗口，讓后進行判斷是否相同就行

class Solution {
    public List<Integer> findAnagrams(String ss, String pp) {
        List<Integer> ret = new ArrayList<>();

        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        //使用兩個數(shù)組來模擬hash
        int[] hash1 = new int[26];//用來放pp字符串的所有字符信息
        for(char ch : p){
            hash1[ch - 'a']++;
        }
        int[] hash2 = new int[26];//此時的用來放窗口中每個字符出現(xiàn)的次數(shù)
        int n = pp.length();
        //此時的count是用來統(tǒng)計有效字符個數(shù)
        for(int left = 0,right = 0,count = 0;right<ss.length();right++){
            char in = s[right];
            if(++hash2[in - 'a'] <= hash1[in - 'a']){//入窗口
                count++;
            }
            //判斷
            if(right - left + 1 > n){
                //出窗口
                char out = s[left++];
                if(hash2[out - 'a']-- <= hash1[out - 'a']){
                    count--;
                }
            }
            //更新結(jié)果
            if(count == n){
                ret.add(left);
            }
        }
        return ret;
    }
}

時間復雜度：O(N+M) ,兩個字符串串長度
空間復雜度：O(N) ， s字符串長度

串聯(lián)所有單詞的子串

題目解析：就是在一個s字符串中找出包含words中所有單詞，并返回所有下標，
算法原理：此題目和上一題：找出所有字母的異位詞是一樣的意思，只不過我們此時這里的字母變成了單詞，因此這個題目和上一個原理一樣，只不過此時要注意將其單詞看成一個整體，這樣就和上一個題目一樣了

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret = new ArrayList<>();

        //使用map來存放words
        Map<String,Integer> hash1 = new HashMap<>();
        for(String word : words){
            hash1.put(word,hash1.getOrDefault(word,0)+1);
        }
        int n = words[0].length();//單詞長度

        int m = words.length;//有多少單詞
        //此時要循環(huán)n次滑動窗口，因為我們將每個單詞這些字符看成了一個整體放入hash
        for(int i = 0;i < n;i++){
            //使用count來統(tǒng)計有效單詞個數(shù)
            Map<String,Integer> hash2 = new HashMap<>();
            for(int left = i,right = i,count = 0;right <= s.length() - n;right += n){
                String in = s.substring(right,right+n);
                hash2.put(in,hash2.getOrDefault(in,0)+1);
                if(hash2.get(in) <= hash1.getOrDefault(in,0)){
                    count++;
                }

                //出窗口
                if(right - left + 1 > m*n){
                    String out = s.substring(left,left+n);
                    if(hash2.get(out) <= hash1.getOrDefault(out,0)){
                        count--;
                    }
                    hash2.put(out,hash2.get(out) - 1);
                    if(hash2.get(out) == 0){
                        hash2.remove(out);
                    }
                    left += n;
                }
                if(count == m){
                    ret.add(left);
                }
            }
        }
        return ret;
    }
}

時間復雜度：O( m * n)
空間復雜度：O( n )
n是words數(shù)組長度，m是s的長度

最小覆蓋子串

題目解析：在s這個字符串中找到一個最下子串，并且其中每個字母數(shù)量要不小于t中的
算法原理：
暴力解法：雙重for循環(huán)+hash，雙重for循環(huán)遍歷所有情況，用hash存放，并有方法來判斷其是否符合條件
滑動窗口+hash：left = 0 , right = 0;暴力解法中，我們遇到滿足情況進行更新結(jié)果時候，其實并不需要將其right從新返回left，重新放入hash中，我們只需要將left下標對應字符出去就行，因為此時只會出現(xiàn)兩種情況1.還滿足條件right不動2.不滿足條件 right繼續(xù)右移

class Solution {
    public String minWindow(String ss, String tt) {
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();

        //使用數(shù)組來模擬hash
        int[] hash1 = new int[128];
        int kinds = 0;//記錄tt中出現(xiàn)字符的種類
        for (char ch : t) {
            if (hash1[ch]++ == 0) {
                kinds++;
            }
        }

        int minlen = Integer.MAX_VALUE;
        int begin = -1;//記錄其起始位置和長度即可
        int[] hash2 = new int[128];//記錄窗口中字符
        for (int left = 0, right = 0, count = 0; right < ss.length(); right++) {
            char in = s[right];
            //當這個字符的數(shù)量和hash1相同時候，count++
            if (++hash2[in] == hash1[in]) {
                count++;
            }
            while (kinds == count) {
                //更新結(jié)果
                if (right - left + 1 < minlen) {
                    begin = left;
                    minlen = right - left + 1;
                }
                char out = s[left++];
                if (hash2[out]-- == hash1[out]) {
                    count--;
                }
            }
        }
        return begin == -1 ? new String() : ss.substring(begin, begin + minlen);
    }
}