滑动窗口

643. 子数组最大平均数 I

以下会超时 因为每个子数组都要计算一次平均数，复杂度为O(n^2)

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        if(nums.length==1) return (double)nums[0];
        double maxm = 0;
        int fast = k-1;
        int slow = 0;
        while(fast<nums.length){
            double temp = 0;
            for(int i=0;i<k;i++){
                temp+= nums[slow+i];
            }
            temp = temp/k;
            if(temp>maxm) maxm = temp;
            fast++;
            slow++;
        }
        return maxm;
    }
}

以下为官方答案 两头更新 中间的保留

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int sum = 0;
        for(int i=0;i<k;i++){
            sum+=nums[i];
        }
        int maxm = sum;
        for(int j=k;j<nums.length;j++){
             sum = sum - nums[j-k] + nums[j];
            if(sum>maxm) maxm = sum;
        }
        return 1.0*maxm/k;
    }
}

1004. 最大连续1的个数 III

⭐

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

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

class Solution {
    public int longestSubarray(int[] nums) {
        int right = 0,left = 0;
        int res = 0;
        int c=0;
        while(right<nums.length){
            if(nums[right]==0) c++;
            while(c>1){
                if(nums[left]==0) c--;
                left++;
            }
            
            res =Math.max(res,right-left);
            right++;
        }
        return res;
    }
}

滑动窗口模版

右指针主动走 左指针通过判断条件被动走

def findSubArray(nums):
    N = len(nums) # 数组/字符串长度
    left, right = 0, 0 # 双指针，表示当前遍历的区间[left, right]，闭区间
    sums = 0 # 用于统计 子数组/子区间 是否有效，根据题目可能会改成求和/计数
    res = 0 # 保存最大的满足题目要求的 子数组/子串 长度
    while right < N: # 当右边的指针没有搜索到 数组/字符串 的结尾
        sums += nums[right] # 增加当前右边指针的数字/字符的求和/计数
        while 区间[left, right]不符合题意: # 此时需要一直移动左指针，直至找到一个符合题意的区间
            sums -= nums[left] # 移动左指针前需要从counter中减少left位置字符的求和/计数
            left += 1 # 真正的移动左指针，注意不能跟上面一行代码写反
        # 到 while 结束时，我们找到了一个符合题意要求的 子数组/子串
        res = max(res, right - left + 1) # 需要更新结果
        right += 1 # 移动右指针，去探索新的区间
return res

3. 滑动窗口

☆

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character,Integer> map = new HashMap<Character,Integer>();
        int maxm = 0;
        int left=0;
        for(int i=0;i<s.length();i++){
            if(map.containsKey(s.charAt(i))){
                left = Math.max(left,map.get(s.charAt(i)));   //max保证left不能往回跳
            }
            map.put(s.charAt(i),i);
            maxm = Math.max(maxm,i-left+1);
        }
        return maxm;
    }
}

438. 比特位计数

很棒！自己调试ac的

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        char charp[] = p.toCharArray();
        Arrays.sort(charp);
        List<Integer> list = new ArrayList<Integer>();
        String p1 = new String(charp);
        int left=0;
        int right=p.length()-1;
        while(right<s.length()){
            String temp = s.substring(left,right+1);
            char charpp[] = temp.toCharArray();
            Arrays.sort(charpp);
            String p2 = new String(charpp);
            if(p1.equals(p2)){
                list.add(left);
            }
            left++;
            right++;
        }
        return list;
    }
}