优选算法合集————双指针(专题二)

好久都没给大家带来算法专题啦，今天给大家带来滑动窗口专题的训练

题目一：长度最小的子数组

题目描述：

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

题目解析：

我们要在给定的数组中找出最短的数的和大于等于target，我们通常可以怎么做呢：

1，暴力解法：

我们直接定义两个下标 left和right，让right向右遍历，遍历到最后3下标，记录大于等于target的最短长度，在让left++，从1下标开始让r从3下标一直走到头记录大于等于target的最短长度，这样的操作时间复杂度还是很大的为O(n方），我们要想一个全新的方法；

算法思路：

我们使用滑动窗口，还是定义两个指针left和right；

1，进窗口：让right的元素相加得到num；

2，判断条件；如果num的值>=target，更新结果，把当前的长度记录下来，此时right原地不动，出窗口：让左边的left下标的元素出去，直到num<=target;

滑动窗口这主要就是想，代码很固定的，进窗口，判断条件，（出窗口，更新结果，这俩的顺序因题而异）；

代码实现：

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int right = 0;
        int n = nums.length;
        int num = 0;
        int len = Integer.MAX_VALUE;
        for(;right<n;right++){
            num+=nums[right];
            while(num>=target){
                len = Math.min(len,right-left+1);
                num-=nums[left];
                left++;
            }
        }
        len = len==Integer.MAX_VALUE?0:len;
        return len;
    }
}

———————————————————————————————————————————

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

题目描述：

给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。

示例 1：

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子字符串是 "abc"，所以其长度为 3。

示例 2：

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子字符串是 "b"，所以其长度为 1。

示例 3：

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

示例 4：

输入: s = ""
输出: 0

题目解析：

和刚才的题差不多，我们得到一个数组我们要统计连续不重复字符的最大长度，我们依旧是可以进行暴力解法，定义两个指针，一次一次遍历找到最长且满足条件的字符串，但是太慢了，我们还是要使用方法；

算法思路：

准备：定义一个数组模拟哈希，为啥不直接用HashMap或者HashSet呢，不断的调用这些方法也很慢，我们直接用数组的话会快很多很多，把字符串s转换成字符数组，个人习惯；

1，进窗口：Hash对应的字符下标+1；

2，更新结果：在判断条件之前就要更新结果，进窗口一次就记录一次结果；

3，判断条件：当进入的right的Hash大于1，就要一直出窗口，直到窗口中没有1重复元素了为止；

代码实现：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] hash1 = new int[10000];
        char[] arr = s.toCharArray();
        int left = 0;
        int right = 0;
        int len = 0;
        int n = arr.length;
        for(;right<n;right++){
            hash1[arr[right]]++;
            while(hash1[arr[right]]>1){
                hash1[arr[left]]--;
                left++;
            }
            len = Math.max(len,right-left+1);
        }
        return len;
    }
}

———————————————————————————————————————————

题目三：最大连续1的个数

题目描述：

给定一个二进制数组 nums 和一个整数 k，假设最多可以翻转 k 个 0 ，则返回执行操作后 数组中连续 1 的最大个数 。

示例 1：

输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。

示例 2：

输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。

题目解析：

还是一样给了一个数组，和一个整数k，我们要找到连续1最大的长度，并且0有k次机会可以翻转为1，我们就可以把k当做一个窗口，小于k进窗口，超过k出窗口；

算法思路：

1，定义count与k比较当作窗口

2，进窗口：如果nums[right]的值为0，count++，为1count不变，

3，判断条件：当count>k，开始循环出窗口直到count<=k，

4，更新结果：在判断条件外中更新结果；

代码实现：

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

———————————————————————————————————————————

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

题目描述：

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。

如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。

示例 1：

输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。

示例 2：

输入：nums = [5,6,7,8,9], x = 4
输出：-1

示例 3：

输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。

题目解析：

这道题也是给我们了个数组和一个整数x，让我们从数组左边或者右边拿一个数来减去x直到让他为0，这题干做的话其实挺难的也不好去想，但是我做题一般看到最大连续，最小连续等等的字样，我就会想到滑动窗口，我们可以反过来想，它要减两边的数，那么我可以加中间的数，它要最小操作数，算中间就是加最大操作数，让x减到零就是把数组所有数加起来减x；

算法思路：

1，把数组所有元素相加减x，就是中间元素的target，

2，进窗口：nums[left]相加，

3，判断条件：当相加的结果大于我们的target就出窗口，减去nums[left]的值，

4，更新结果，当相加的值等于target更新长度

5，注意，left不能超过right；

代码实现：

class Solution {
    public int minOperations(int[] nums, int x) {
        int left=0, right=0, n=nums.length;
        int len=-1, num=0, num2=0;
        for(int i=0;i<n;i++){
            num2+=nums[i];
        }
        int targrt = num2-x;        
        for(;right<n;++right){
            num+=nums[right];
            while(left<=right && num>targrt){
                num-=nums[left];
                left++;
            }
            if(num==targrt){
                len = Math.max(len,right-left+1);
            }
        }
        if(len==-1){
            return -1;
        }
        return n-len;
      
    }
}

———————————————————————————————————————————

题目五：水果成篮

题目描述：

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

• 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
• 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
• 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

示例 1：

输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

示例 2：

输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

示例 3：

输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。

示例 4：

输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。

题目解析：

最讨厌阅读理解了，这到题简单来说，就是给我一个数组，完了你的容器中只允许有两种水果，水果的数量可以一直增加，但是水果的种类就能有两种，我们还是可以用暴力做法一个一个枚举，但是他说最大连续呀，它还有容器（窗口）；

算法思路：

1，创建数组模拟哈希表，count为容量，本题为两个

2，进窗口：hash[fruits[right]]++，另外如果哈希数组为空count++，

3，更新结果：在判断之前就要更新结果；

4，判断条件：如果count>2那么就要出窗口：hash[fruits[left]]--；

代码实现：

class Solution {
    public int totalFruit(int[] fruits) {
        int right = 0, left = 0, n = fruits.length;
        int count = 0, len = 0;
        int[] hash = new int[100000];
        for(;right<n;right++){
            if(hash[fruits[right]]==0){
                count++;
            }
            hash[fruits[right]]++;

            while(count>2){
                hash[fruits[left]]--;
                if(hash[fruits[left]]==0){
                    count--;
                }
                left++;
            }

            len = Math.max(len,right-left+1);
        }
        return len;
    }
}

———————————————————————————————————————————

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

题目描述：

给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

变位词 指字母相同，但排列不同的字符串。

示例 1：

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的变位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的变位词。

 示例 2：

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的变位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的变位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的变位词。

题目解析：

我们先来了解下异位词，比如abc 那么异位词就是abc，acb，bac，bca，cab，cba，但是只能有该字符串有的元素和元素数量，这道题就是让我们在字符串中找到所给字符串的异位词，这道题挺麻烦的，可以用暴力枚举但是很显然这题的第二个字符串就是窗口，限制了长度也限制了类型那不就是个窗口嘛；

算法思路：

准备：把俩字符串转换为字符数组（习惯），我们定义两个哈希数组，把目标数组遍历，把所有元素放到哈希数组1中备用，开始遍历数组2，有效字母个数count；

1，进窗口：直接Hash[s[right]]++，这时候判断if(   hash2[s[right]]<=hash1[s[right]]  )时 ，count++，因为只有Hash2中的元素小于等于Hash1时进窗口才会有效，count才能加加，其他任何情况都不行；

2，判断条件：当现在判断的长度大于目标数组长度时，就是right-left+1>目标数组长度，

我们先判断如果出的元素是目标数组中的元素，我们就count--，就是hash2[s[left]]<=hash1[s[left]]的时候，之后让Hash[s[left]]--；left++；

3，更新结果：当有效字母count==目标数组长度时就能更新了

代码实现：

class Solution {
    public List<Integer> findAnagrams(String ss, String pp) {
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        int right = 0, left = 0;
        int ns = s.length, np = p.length;
        List<Integer> list1 = new ArrayList<>();
        int[] hash1 = new int[256];
        int[] hash2 = new int[256];
        int count = 0;

        for(int i=0;i<np;i++){
            hash1[p[i]]++;
        }

        for(;right<ns;right++){
            hash2[s[right]]++;
            if(hash1[s[right]]>=1 && hash2[s[right]]<=hash1[s[right]]){
                count++;
            }
            if(right-left+1>np){
                if(hash1[s[left]]>=1 && hash2[s[left]]<=hash1[s[left]]){
                    count--;
                }
                hash2[s[left]]--;
                left++;
            }

            if(count==np){
                list1.add(left);
            }
        }
        return list1;
    }
}

———————————————————————————————————————————

题目七：串联所有单词的子串

题目描述：

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

 s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。

• 例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1：

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2：

输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3：

输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

题目解析：

这题噶比恶心，不是思路难是细节太多太多了，这题跟6题基本上差不多，但是目标数组变成了字符串数组，我们不是一个一个字符判断了，而是两个两个或者三个三个或更多；

算法思路：

准备：计算出目标数组的数组长度nw，和每个单词的长度num，准备两个哈希表Hash1放目标数组，Hash2放遍历数组，有效字符串个数count，执行次数k，这个k是个什么玩意，我们不是要在一组字符串中找这个目标数组符合要求的字符串吗，我们要遍历的数组并不是字符串而是一个一个的字符，我们从第一个字符开始和从第二个字符开始遍历每次截取的结果是不一样的，我弄个图，这说的太绕了：

我们目标数组的长度为2，我们每次遍历都是两个两个的，比如从0下标开始：

我们就会这样遍历完数组最终找到2下标为题目要求的，那么从1下标呢：

又是一组新的遍历结果，再从2下标呢：

结果是和0下标重复的，甚至少了一个，所以我们要进行k（次数）<num（目标数组每个单词的长度）次，最后的准备，把目标元素全部放到Hash1中；

1，进窗口：（先进后判断）Hash2.put(...........) 

if(hash2.getOrDefault(in,0)<=hash1.getOrDefault(in,0)){

                    count++;

                }

这块就和上一题一样

2，判断条件：当right-left+1(当前遍历长度)  >  （目标数组个数*一个多长）nw*num时开始出窗口：先出窗口后判断

if(hash2.getOrDefault(out,0)<=hash1.getOrDefault(out,0)){

                        count--;

                    }

操作有效单词个数；

3，更新结果：当count==nw    把有序的left添加到链表中；

代码实现：

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list1 = new ArrayList<>();
        int left = 0, right = 0;
        int ns = s.length(), nw = words.length;
        HashMap<String,Integer> hash1 = new HashMap<>();
        int count = 0;
        int num = words[0].length();
        int k = 0;

        for(int i=0;i<nw;i++){
            hash1.put(words[i],hash1.getOrDefault(words[i],0)+1);
        }

        while(k<num){
            right = k;
            left = k;
            count = 0;
            HashMap<String,Integer> hash2 = new HashMap<>();
            for(;right+num<=ns;right+=num){
                String in = s.substring(right,right+num);
                hash2.put(in,hash2.getOrDefault(in,0)+1);
                if(hash2.getOrDefault(in,0)<=hash1.getOrDefault(in,0)){
                    count++;
                }
                if(right-left+1>nw*num){
                    String out = s.substring(left,left+num);
                    if(hash2.getOrDefault(out,0)<=hash1.getOrDefault(out,0)){
                        count--;
                    }
                    hash2.put(out,hash2.getOrDefault(out,0)-1);
                    left+=num;
                }
                if(count==nw){
                    list1.add(left);
                }
            }
            k++;
        }
        return list1; 

    }
}

———————————————————————————————————————————

题目八：最小覆盖子串

题目描述：

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

题目解析：

难度下来啦，这题让我们在一组字符中只要找到有一串字符包含目标数组中几个元素就行了，既然最小连续，那么必定滑动窗口；

算法思路：

准备：模拟两个哈希表使用哈希数组（注意是快），把目标数组中所有元素放到哈希数组1

1，进窗口：将要遍历数组的每个元素放到Hash2如果

if(hash2[s[right]]<=hash1[s[right]]){
                count++;
            }

不解释了，好几遍了，

2，判断条件并更新结果：这里当count==目标数组长度就更新结果并出窗口：

if(hash2[s[left]]<=hash1[s[left]]){

                    count--;

                }

有效字母判断别忘了；

代码实现：

class Solution {
    public String minWindow(String ss, String tt) {
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();
        int left = 0, right = 0;
        int ns = s.length, nt = t.length;
        int len = Integer.MAX_VALUE;
        int count = 0;
        int[] hash1 = new int[256];
        int[] hash2 = new int[256];
        int a=0;
        int b=0;

        for(int i = 0;i<nt;i++){
            hash1[t[i]]++;
        }

        for(;right<ns;right++){
            hash2[s[right]]++;
            if(hash2[s[right]]<=hash1[s[right]]){
                count++;
            }


            while(count==nt){
                if(right-left+1<len){
                    len = right-left+1;
                    a = left;
                    b = right;
                }
                if(hash2[s[left]]<=hash1[s[left]]){
                    count--;
                }
                hash2[s[left]]--;
                left++;
            }
        } 
        if(len==Integer.MAX_VALUE){
            return "";
        }
        return ss.substring(a,b+1);
    }
}