leetcode滑动窗口

Bertha 。 2022-09-04 09:53 187阅读 0赞

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

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

输入: s = “abcabcbb”  
输出: 3

采用滑动窗口搜索字符串，使用hashset存储当前子串中包含的字符。  
向右滑动时，判断右侧字符是否在hashset中（contain方法判断是否重复），如果重复的话，则将左端向右移动，同时从hashset中移除左端所指的字符，并将右侧字符存入hashset之中。

class Solution {
        
        public int lengthOfLongestSubstring(String s) {
        
        int n = s.length();
        if (n <= 1) return n;//特判
        int maxLen = 1;
    
        int left = 0, right = 0;
        Set<Character> window = new HashSet<>();
        while (right < n) {
        
            char rightChar = s.charAt(right);
            while (window.contains(rightChar)) {
        
                window.remove(s.charAt(left));
                left++;
            }
            maxLen = Math.max(maxLen, right - left + 1);
            window.add(rightChar);
            right++;
        }
    
        return maxLen;
        }
    }

1.  找到字符串中所有字母异位词

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

异位词 指字母相同，但排列不同的字符串。  
输入: s = “cbaebabacd”, p = “abc”  
输出: \[0,6\]  
解释:  
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。  
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。

异位词只需要每个字母出现的次数相同即可，与顺序无关。  
建立两个数组存储目标值与当前子串的字母情况。

class Solution {
        
        public List<Integer> findAnagrams(String s, String p) {
        
        int l1=s.length();int l2=p.length();
        List list=new ArrayList();
        if(l1>=l2)
        {
        int left=0;int right=l2-1;
        int cnt1[]=new int[26];
        int cnt2[]=new int[26];
        for(int i=0;i<l2;i++){
        
            cnt1[s.charAt(i)-'a']++;
            cnt2[p.charAt(i)-'a']++;
        }//
        
        if(Arrays.equals(cnt1,cnt2))
        {
        list.add(0);}//第一步就相等，则将索引0加入。
        for(int i=0;i<l1-l2;i++){
        //滑动过程，滑块长度固定，与上题不固定长度区别。
            cnt1[s.charAt(left)-'a']--;
            left++;
            right++;
            cnt1[s.charAt(right)-'a']++;
            if(Arrays.equals(cnt1,cnt2)){
        
                list.add(left);//找到，加入。
            }
        }}
        return list;
        }
    }

1.  长度最小的子数组

给定一个含有 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

滑动窗口解决。

class Solution {
        
        public int minSubArrayLen(int target, int[] nums) {
        
        int ans=999999999;
        int l=nums.length;
        int left=0;int right=0;
        int res=0;
        int flag=0;
        while(right<l){
        
            res+=nums[right];
            while(res>=target){
        
                ans=Math.min(ans,right-left+1);
                flag=1;
                res-=nums[left];
                left++;
            }
            right++;
        }
        if(flag==0)return 0;
        return ans;
        }
    }

1.  乘积小于K的子数组

给定一个正整数数组 nums和整数 k 。

请找出该数组内乘积小于 k 的连续的子数组的个数。

示例 1:

输入: nums = \[10,5,2,6\], k = 100  
输出: 8  
解释: 8个乘积小于100的子数组分别为: \[10\], \[5\], \[2\], \[6\], \[10,5\], \[5,2\], \[2,6\], \[5,2,6\]。  
需要注意的是 \[10,5,2\] 并不是乘积小于100的子数组。

class Solution {
        
        public int numSubarrayProductLessThanK(int[] nums, int k) {
        
            if (k <= 1) return 0;
            int prod = 1, ans = 0, left = 0;
            for (int right = 0; right < nums.length; right++) {
        
                prod *= nums[right];
                while (prod >= k) prod /= nums[left++];
                ans += right - left + 1;
            }
            return ans;
        }
    }

正常使用滑动窗口，但计数方式ans+=right-left+1是关键。  
right-left+1的切入点是思维要放在区间的右边往左边延伸，例如区间\[1, 2, 3, 4\]满足要求，固定住right(4)的点，可选区间右\[4\]、\[4, 3\]、\[4, 3, 2\]、\[4, 3, 2, 1\]即为数组的长度，也就是right-left+1。而right是递增的，此时\[1, 2, 3\]的区间已经处理完（\[3\]、\[3, 2\]、\[3、2、1\]）。如果从left为切入点，就会有\[1, 2, 3, 4\]和\[1, 2, 3\]都有\[1\]，不就是重复了的错乱思维。