算法学习笔记（一）：滑动窗口和双指针

滑动窗口套路：

        核心套路三步骤：

                1.入： 下标为 i 的元素进入窗口，更新相关统计量(因为一个元素进入了，则相关统计的数据要更新，就是+)，然后进行判断，如果i < k - 1 则continue，继续进入窗口，因为定长窗口元素不足；

                2.更新：更新答案。一般是更新最大\最小值；

                3.出：下标为i - k + 1 的元素离开窗口，更新相关统计量(出了一个元素，窗口内的统计量要减去这个出的元素)。

一：定长滑动窗口

1.定长字串中元音的最大数目

        元音有：a\e\i\o\u

        给你字符串 S 和整数 k；

        请你返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。

class Solution {
    public int maxVowels(String s, int k) {
        int max = Integer.MIN_VALUE;
        int sum = 0;
        char[] arr = s.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            //入
            if (isVowel(arr[i])) sum++;
            if (i < k - 1) continue;
            //更新
            max = Math.max(sum, max);
            //出
            char out = arr[i - k + 1];
            if (isVowel(out)) sum--;
        }
        return max;
    }

    public boolean isVowel(char ch) {
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
    }
}

2.子数组最大平均数I

        给你一个由 n 个元素组成的整数数组 nums 和一个整数 k

        请你找出平均数最大且长度为 k 的连续子数组，并输出该最大平均值

        任何误差小于 10(-5)的答案都将被视为正确答案

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int maxAvg = Integer.MIN_VALUE, sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (i < k - 1) continue;
            maxAvg = Math.max(maxAvg, sum);
            sum -= nums[i - k + 1];
        }
        return 1.0 * maxAvg / k;
    }
}

3.大小为 k 且平均值大于等于阈值的子数组数目

        给你一个整数数组 arr 和两个整数 k 和threshold

        请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。

class Solution {
    public int numOfSubarrays(int[] arr, int k, int threshold) {
        int avg = 0, count = 0;
        for (int i = 0; i < arr.length; i++) {
            avg += arr[i];
            if (i < k - 1) continue;
            if (avg / k >= threshold) count++;
            avg -= arr[i - k + 1];
        }
        return count;
    }
}

4.得到 K 个黑块的最少涂色次数

        给你一个长度为 n 下标从 0 开始的字符串 blocks，blocks[i] 要么是 ‘W’ 要么是 ‘B’，表示白色和黑色

        给你一个整数 k，表示想要连续黑色快的数目

        每一次操作中，你可以选择一个白色快将它涂成黑色快

        请你返回至少出现一次连续 k个黑色快的最少操作次数

class Solution {
    public int minimumRecolors(String blocks, int k) {
        int min = Integer.MAX_VALUE, count = 0;
        char [] arr = blocks.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 'W') count++;
            if (i < k - 1) continue;
            min = Math.min(min, count);
            char out = arr[i - k + 1];
            if (out == 'W') count--;
        }
        return min;
    }
}

二：不定长滑动窗口

1.无重复字符的最长字串

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

class Solution {
    public int lengthOfLongestSubstring(String s) {
        //用哈希表或者数组存重复字符的上一个索引
        Map<Character, Integer> map = new HashMap<>();
        char[] arr = s.toCharArray();
        int left = -1;  //开始从-1开始 表示没有重复元素
        int len = 0;
        for (int i = 0; i < arr.length; i++) {
            if (map.containsKey(arr[i])) {  //有重复的 那么就将left起点从上一个重复的为止开始算长度
                left = Math.max(left, map.get(arr[i])); //这是防止多个重复 比如 abba b先重复了 left已经再1了 这个时候a
                                                        //重复了 a的上一个位置还在0 但是不能从0开始算 要从1开始算
            }
            //更新最新字符的索引
            map.put(arr[i], i);
            len = Math.max(len, i - left);
        }
        return len;
    }
}

2.每个字符最多出现两次的最长子字符串

        给你一个字符串 s，请找出满足每个字符最多出现两次的最长子字符串

        并返回该子字符串的最大长度

class Solution {
    public int maximumLengthSubstring(String s) {
        //这特么是简单题？ 
        /**
            不定长滑动窗口 因为这题说了是由小写字母组成 可以用阿斯克吗来做
            或者用哈希？
            想一想哈希的做法

         */
        // Map<Character, Integer> map = new HashMap<>();
        // int len = 0, left = 0;
        // char[] arr = s.toCharArray();
        // for (int i = 0; i < arr.length; i++) {
        //     map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
        //     while (map.get(arr[i]) > 2) {
        //         //去掉重复字符的第一个
        //         map.put(arr[left], map.get(arr[left]) - 1);
        //         left++;
        //     }
        //     len = Math.max(len, i - left + 1);
        // }
        // return len;

        //用数组来做 效率一点
        int[] arr = new int[26];
        char[] c = s.toCharArray();
        int len = 0, left = 0;
        for (int i = 0; i < c.length; i++) {
            int j = c[i] - 'a'; //正好对应索引下标a从0开始
            arr[j]++;
            while (arr[j] > 2) {
                arr[c[left++] - 'a']--; //不管元素是什么，只要保证left从0开始遍历，一直到找到j这个元素 然后删掉它
                                        //这个时候的left++就是新的开端 就是找到第一个重复的元素 删掉他 然后从它下一个开始
            }
            len = Math.max(len, i - left + 1);
        }
        return len;
    }
}

    3.删掉一个元素以后全为 1 的最长子数组 

            给你一个二进制数组 nums，你需要从中删掉一个元素

                请你在删掉元素的结果数组种，返回最长的且只包含1的非空子数组的长度

                如果不存在这样的子数组，请返回0

class Solution {
    public int longestSubarray(int[] nums) {
        int len = 0, sum = 0, left = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += 1- nums[i];  //如果是0 那么肯定是+1了 相当于判断是否是0
            while (sum > 1) {
                //表示最少进来了两个0了，那么需要删掉最开始的那个0
                sum -= 1- nums[left++];
            }
            len = Math.max(len, i - left);
        }
        return len;
    }
}

二.相向双指针

两个指针left=0，right = n - 1，从数组的两端开始，向中间移动，这叫相向双指针。

1.反转字符串

        编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出

        不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用0(1)的额外空间解决

        这一问题

class Solution {
    public void reverseString(char[] s) {
        /**
            双指针？ 从左和从右开始同时移动，然后右边和左边的值互换
            然后当左>=右了就停下 
         */
        int left = 0, right = s.length - 1;
        while (left < right) {
            char temp = s[left];
            s[left++] = s[right];
            s[right--] = temp;
        } 
    }
}

2.验证回文串

        如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读

        和反着读都一样。则可以认为改短语是一个 回文串

        字母和数字都属于字母数字字符

        给你一个字符串 s，如果它是回文串，返回true，否则返回false

class Solution {
    public boolean isPalindrome(String s) {
        //先大写转小写， 然后去掉非字母数字字符 用ascii码
        //字母ASCII码是97-122 数字0-9的ASCII码是48到57
        s = s.toLowerCase();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if ((c >= 48 && c <= 57) || (c >= 97 && c <= 122)) {
                sb.append(c);
            }
        }
        //验证回文串
        int left = 0, right = sb.length() - 1;
        String str = sb.toString();
        while (left < right) {
            char c = str.charAt(left);
            if (str.charAt(left++) != str.charAt(right--)) return false;
        }
        return true;
    }
}

3.删除字符串两端相同字符后的最短长度

        给你一个只包含字符 ‘a’、‘b’、'c' 的字符串 s，你可以执行下面这个操作任意次：

        1.选择字符串 s的一个非空的前缀，这个前缀的所有字符都相同

        2.选择字符串 s的一个非空的后缀，这个后缀的所有字符都相同

        3.前缀和后缀在字符串种任意位置都不能有交集

        4.前缀和后缀包含的所有字符都要相同

        5.同时删除前缀和后缀

        请你返回堆字符串 s 执行上面操作任意次以后(可能是0次)，能得到的最短长度

class Solution {
    public int minimumLength(String s) {
        /**
            就是前后消消乐，只要前后有相同的字符就全删掉，然后没有相同了就返回剩下的字符串长度
            双指针，前后相同的话，left++ 一直到不相同或者left和right相遇了
            同理 right-- 一直到不相同或者和left相遇
            最后计算right和left的长度+1 因为是表示索引 length是相减+1
         */
        int left = 0, right = s.length() - 1;
        while (left < right && s.charAt(left) == s.charAt(right)) {
            char c = s.charAt(left);
            while (left <= right && s.charAt(left) == c) left++;
            while (left <= right && s.charAt(right) == c) right--;
        }
        return right - left + 1;
    }
}

4. 有序数组的平方

        给你一个按 非递减顺序 排序的整数数组 nums，返回每个数字的平方组成的新数组，

        要求也按 非递减顺序 。

class Solution {
    public int[] sortedSquares(int[] nums) {
        int left = 0, right = nums.length - 1;
        int[] arr = new int[nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            int l = nums[left] * nums[left];
            int r = nums[right] * nums[right];
            if (l > r) {
                arr[i] = l;
                left++;
            } else {
                arr[i] = r;
                right--;
            }
        }
        return arr;
    }
}

5.两数之和II -输入有序数组

        给你一个下标从 1 开始的证书数组 numbers，该数组已按 非递减顺序排列，请你从数组种

        找到满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1]

        和 numbers[index2]，则 1<= index1 < index2 <= numbers.length

        以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2

        你可以假设每个输入 只对应唯一的答案，而且你 不可以重复使用相同的元素

        你所涉及的解决方案必须只能使用常量级的额外空间。 

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        //使用哈希
        // Map<Integer, Integer> map = new HashMap<>();
        // for (int i = 0; i < numbers.length; i++) {
        //     int right = target - numbers[i];
        //     if (map.containsKey(right)) {
        //         return new int[]{i + 1, map.get(right)};
        //     }
        //     map.put(numbers[i], i + 1);
        // }
        // return null;
        //优化 因为是需要输出有序
        int left = 0, right = numbers.length - 1;
        int[] arr = new int[2];
        while (left < right) {
            int temp = numbers[left] + numbers[right];
            if (target == temp ) break;
            if (temp < target) {
                left++;
            } else {
                right--;
            }
        }
        arr[0] = left + 1;
        arr[1] = right + 1;
        return arr;
    }
}

6.平方数之和

        给定一个非负整数 c，判断是否存在两个整数 a 和 b，使得 a2 + b2 = c

class Solution {
    public boolean judgeSquareSum(int c) {
        //想象成两数之和  用c的根作为基数来判断
        int a = 0, b = (int)Math.sqrt(c);
        while (a <= b) {
            if (a * a == c - b * b) return true;
            if (a * a < c - b * b) {
                a++;
            } else {
                b--;
            }
        }
        return false;
    }
}

7.统计和小于目标的下标对数目

        给你一个下标从 0 开始长度为 n的整数数组 nums 和一个整数target，请你返回

        满足 0 <= i < j < n且 nums[i] + nums[j] < target的下标对(i, j) 的数目

class Solution {
    public int countPairs(List<Integer> nums, int target) {
        //因为只是输出对数 不需要index 所以排序之和不影响
        Collections.sort(nums);
        int count = 0, left = 0, right = nums.size() - 1;
        while (left < right) {
            if (nums.get(left) + nums.get(right) < target) {
                //因为排序了 所以这个区间内的对数都满足
                count += right - left;
                left++;
            } else {
                right--;
            }
        }
        return count;
    }
}

8.三数之和

        给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足

        i != j、i != k 且 j != k，满足还满足 nums[i] + nums[j] + nums[k] == 0。

        请你返回所有和为 0 且不重复的三元组、

        注意：答案中不可以包含重复的三元组。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        /**
            固定指针+双指针 从0开始 然后left=i+1 right = n-1
            先排序 
            接下来就是先判断重复的情况
            i = i + 1 则continue i++
            left = left +1 left++
            right = right-1 right--
            然后满足 i+left+right = 0 left++ right--
            如果 < 0 left++ >0 right--
        
         */
    
        List<List<Integer>> lists = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0 ) return lists;
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    lists.add(list);
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++;
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return lists;
    }
}

三.同向双指针

        两个指针的移动方向相同

1.最短无序连续子数组

        给你一个整数数组 nums，你需要找出一个连续子数组，如果对这个子数组进行升序排序，

        那么整个数组都会变成升序排序

        请你找出符合题意得 最短 子数组，并输出它得长度。

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        /**
            边界双指针解法
            可以把数组抽象成三段，前、中、后
            前的长度>=0 这段肯定是有序的
            中的长度>=0 这段肯定是无序的
            后的长度>=0 这段肯定是有序的
            目的就是找出中段的长度 最极限的情况就是要么是0要么是整个数组的length
            怎么确定中段范围呢，找出两个临界值 begin和end
            从begin开始，begin前面的都是比begin小的，begin后面的begin+1肯定是大于begin的 无序的开始
            然后到end结束，end后面的肯定都是比end大的
            然后中段的长度就是end-begin+1 算长度都需要+1   
            begin从右到左遍历 确定begin的位置
            end从左到右遍历 确定end的位置
         */
        int len = nums.length;
        int min = nums[len - 1], begin = 0;
        int max = nums[0], end = -1;       
        for (int i = 0; i < len; i++) {
            //从左右到算end
            if (nums[i] < max) {
                end = i;                
            } else {
                max = nums[i];
            }
            //从右到左算begin
            if (nums[len - i - 1] > min) {
                begin = len - i - 1;               
            } else {
                min = nums[len - i - 1];
            }
        }
        return end - begin + 1;
    }
}

四.双序列双指针

1.合并两个有序数组

        给你两个按 非递减顺序 排列的整数数组 nums1和nums2，另外有两个整数 m 和 n，分别

        表示 nums1和nums2中的元素数目

        请你合并 nums2到nums1中，使得合并后的数组同样按 非递减顺序 排列

        注意：最终合并后的数组不应由函数返回，而是存储在nums1中，为了应对这种情况

        nums1的初始长度为m+n，其中前m个元素表示应合并的元素，后n个元素为0

        应忽略，nums2的长度为n。

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        /**
            因为nums1和nums2已经是递增排序过了的
            所以换个角度，从大到小开始插入，因为nums1的后面肯定是空的 所以从尾部插入大的
            谁大先插入谁 然后指针--
        
         */

        int a = m - 1, b = n - 1;
        int max = m + n - 1;
        while (b >= 0) {    //因为是nums2插入nums1所以最后结束肯定nums已经空了才算完成插入
            //大的插入
            if (a >= 0 && nums1[a] > nums2[b]) {
                nums1[max--] = nums1[a--];
            } else {
                nums1[max--] = nums2[b--];
            }
        }
    }
}

2.判断子序列

        给定字符串 s 和 t，判断s是否为 t的子序列

        字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符

        相对位置形成的新字符串

        例如：“ace”是“ancde”的一个子序列，而“aec”并不是

class Solution {
    public boolean isSubsequence(String s, String t) {
        /**
            双指针 一个从s0开始 一个从t0开始
            相等 都++
            不等 s原地等候 t++
            最后s=s.length或者t=t.length退出循环
            最后判断 s==s.length ==就是走完了 那么肯定是字串
         */
        int sIndex = 0, tIndex = 0;
        while (sIndex < s.length() && tIndex < t.length()) {
            if (s.charAt(sIndex) == t.charAt(tIndex)) {
                sIndex++;
                tIndex++;
            } else {
                tIndex++;
            }
        }
        return sIndex == s.length();
    }
}