滑动窗口专题

Mr.He...

lc-219 Easy

使用set作为滑动窗口，通过下标判断窗口大小。

遍历数组，使用set来保存遍历过的元素。通过set的大小，或遍历时的下班与k比较，来动态移除先前加进去的元素。如果添加失败，表示遇到了重复元素，返回true。遍历完成仍没有结束的，表示k范围内没有重复元素，返回false。

public boolean containsNearbyDuplicate(int[] nums, int k) {
    Set<Integer> set = new HashSet<>();
    int length = nums.length;
    for (int i = 0; i < length; i++) {
        if (i > k) {
            set.remove(nums[i-k-1]);
        }
        if (!set.add(nums[i])) {
            return true;
        }
    }
    return false;
}

时间 O(n)

空间 O(k) set中的元素数，最多为k+1个。

lc-643 Easy

求最大平均值，其实就是求子数组最大和。使用cur来记录窗口内元素的和，并使用max来记录不同下标处的和的最大值即可。
易错点：max可以初始化为0，但在循环内，k之前的元素都要加起来才是第一个max的值。

public double findMaxAverage(int[] nums, int k) {
    int max = 0, cur = 0;
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        if (i >= k) {
            cur = cur - nums[i-k] + nums[i];
            max = Math.max(max, cur);
        } else {
            cur += nums[i];
            max = cur;
        }
    }
    return 1.0 * max / k;
}

lc-1876 Easy

可以用滑动窗口，但是没必要。

public int countGoodSubstrings(String s) {
    int sum = 0;
    int n = s.length();
    char[] chars = s.toCharArray();
    for (int i = 0; i <= n-3; i++) {
        if (chars[i] != chars[i+1] && chars[i]!= chars[i+2] && chars[i+1] != chars[i+2]) {
            sum++;
        }
    }
    return sum;
}

lc-1984 Easy

可以先给学生分数排序，再构造一个大小为k的滑动窗口。从左到右遍历一次排序后的数组，找出每个窗口首位两端的分数差，最后找出所有窗口中分数差最小的值即可。

public int minimumDifference(int[] nums, int k) {
    Arrays.sort(nums);
    int n = nums.length, ret = nums[k-1] - nums[0];    
    for (int i = k; i < n; i++) {
        ret = Math.min(ret, nums[i] - nums[i-k+1]);
    }
    return ret;
}

时间：O(nlogn)。n是数组长度，排序需要的时间为 O(nlogn)，后续遍历需要 O(n)

空间：O(logn)，即排序需要的栈空间

lc-1658Mid

和上面的滑动窗口不同，这道题需要计算的是数组两侧的数字和，即“窗口之外”的数。

public int minimumDifference(int[] nums, int k) {
    Arrays.sort(nums);
    int n = nums.length, ret = nums[k-1] - nums[0];    
    for (int i = k; i < n; i++) {
        ret = Math.min(ret, nums[i] - nums[i-k+1]);
    }
    return ret;
}