定长滑动窗口 part02

算法

2841. 几乎唯一子数组的最大和

题目描述

给你一个整数数组 nums 和两个正整数 m 和 k 。

请你返回 nums 中长度为 k 的 几乎唯一 子数组的 最大和 ，如果不存在几乎唯一子数组，请你返回 0 。

如果 nums 的一个子数组有至少 m 个互不相同的元素，我们称它是 几乎唯一 子数组。

子数组指的是一个数组中一段连续非空的元素序列。

示例

输入：nums = [5,9,9,2,4,5,4], m = 1, k = 3输出：23解释：总共有 5 个长度为 k = 3 的几乎唯一子数组。分别为 [5, 9, 9] ，[9, 9, 2] ，[9, 2, 4] ，[2, 4, 5] 和 [4, 5, 4] 。这些子数组中，和最大的是 [5, 9, 9] ，和为 23 。

解题思路

class Solution {
    public long maxSum(List<Integer> nums, int m, int k) {
        long ans = 0;
        long sum = 0;
        int n = nums.size();
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int inKey = nums.get(i);
            sum += inKey;
            map.put(inKey, map.getOrDefault(inKey, 0) + 1);
            if (i < k - 1) {
                continue;
            }
            if (map.size() >= m) {
                ans = Math.max(sum, ans);
            }
            int outKey = nums.get(i - k + 1);
            sum -= outKey;
            if (map.get(outKey) == 1) {
                map.remove(outKey);
            } else {
                map.put(outKey, map.get(outKey) - 1);
            }
        }

        return ans;
    }
}

2461. 长度为 K 子数组中的最大和

题目描述

给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：

子数组的长度是 k，且
子数组中的所有元素 各不相同。

返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。

子数组 是数组中一段连续非空的元素序列。

示例

输入：nums = [1,5,4,2,9,9,9], k = 3输出：15解释：nums 中长度为 3 的子数组是：

[1,5,4] 满足全部条件，和为 10 。

[5,4,2] 满足全部条件，和为 11 。

[4,2,9] 满足全部条件，和为 15 。

[2,9,9] 不满足全部条件，因为元素 9 出现重复。

[9,9,9] 不满足全部条件，因为元素 9 出现重复。因为 15 是满足全部条件的所有子数组中的最大子数组和，所以返回 15 。

解题思路

class Solution {
    public long maximumSubarraySum(int[] nums, int k) {
        int n = nums.length;
        long ans = 0, sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int inKey = nums[i];
            sum += inKey;
            map.put(inKey, map.getOrDefault(inKey, 0) + 1);

            if (i < k - 1) continue;
          
            int outKey = nums[i - k + 1];
            if (map.size() == k) {
                ans = Math.max(sum, ans);
            }
            if (map.get(outKey) == 1) {
                map.remove(outKey);
            } else {
                map.put(outKey, map.get(outKey) - 1);
            }
            sum -= outKey;
        }
        return ans;
    }
}

1423. 可获得的最大点数

题目描述

几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。

每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。

你的点数就是你拿到手中的所有卡牌的点数之和。

给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。

示例

输入：cardPoints = [1,2,3,4,5,6,1], k = 3输出：12解释：第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5 = 12 。

解题思路

逆向思维求解

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        // 逆向：求 n-k 窗口的最小值，用total减
        k = n - k;
        int total = 0;
        for (int i = 0; i < k; i++) {
            total += cardPoints[i];
        }

        int minSum = total, sum = total;
        for (int i = k; i < n; i++) {
            total += cardPoints[i];
            sum += cardPoints[i] - cardPoints[i - k];
            minSum = Math.min(sum, minSum);
        }
        return total - minSum;
    }
}

1176. 健身计划评估

题目描述

你的好友是一位健身爱好者。前段日子，他给自己制定了一份健身计划。现在想请你帮他评估一下这份计划是否合理。

他会有一份计划消耗的卡路里表，其中 calories[i] 给出了你的这位好友在第 i 天需要消耗的卡路里总量。

为了更好地评估这份计划，对于卡路里表中的每一天，你都需要计算他「这一天以及之后的连续几天」（共 k 天）内消耗的总卡路里 T：

如果 T < lower，那么这份计划相对糟糕，并失去 1 分；
如果 T > upper，那么这份计划相对优秀，并获得 1 分；
否则，这份计划普普通通，分值不做变动。

请返回统计完所有 calories.length 天后得到的总分作为评估结果。

注意：总分可能是负数。

示例

输入：calories = [1,2,3,4,5], k = 1, lower = 3, upper = 3输出：0解释：calories[0], calories[1] < lower 而 calories[3], calories[4] > upper, 总分 = 0.

解题思路

class Solution {
    public int dietPlanPerformance(int[] calories, int k, int lower, int upper) {
        int ans = 0, T = 0;
        int n = calories.length;

        for (int i = 0; i < n; i++) {
            T += calories[i];

            if (i < k - 1) {
                continue;
            }

            if (T < lower) {
                ans--;
            } else if (T > upper) {
                ans++;
            }

            T -= calories[i - k + 1];
        }

        return ans;
    }
}

1100. 长度为 K 的无重复字符子串

题目描述

给你一个字符串 S，找出所有长度为 K 且不含重复字符的子串，请你返回全部满足要求的子串的数目。

示例

输入：S = "havefunonleetcode", K = 5输出：6解释：这里有 6 个满足题意的子串，分别是：'havef','avefu','vefun','efuno','etcod','tcode'

解题思路

class Solution {
    public int numKLenSubstrNoRepeats(String s, int k) {
        int ans = 0;
        int n = s.length();
        Map<Character, Integer> map = new HashMap<>();

        for (int i = 0; i < n; i++) {
            char in = s.charAt(i);
            map.put(in, map.getOrDefault(in, 0) + 1);
            if (i < k - 1) continue;

            if (map.size() == k) ans++;

            char out = s.charAt(i - k + 1);
            if (map.get(out) == 1) {
                map.remove(out);
            } else {
                map.put(out, map.get(out) - 1);
            }
        }
        return ans;
    }
}

1852. 每个子数组的数字种类数

题目描述

给你一个长度为 n 的整数数组 nums 与一个整数 k。你的任务是找到 nums 所有长度为 k 的子数组中不同元素的数量。

返回一个数组 ans，其中 ans[i] 是对于每个索引 0 <= i < n - k，nums[i..(i + k - 1)] 中不同元素的数量。

示例

输入: nums = [1,2,3,2,2,1,3], k = 3输出: [3,2,2,2,3]解释：每个子数组的数字种类计算方法如下：

nums[0..2] = [1,2,3] 所以 ans[0] = 3

nums[1..3] = [2,3,2] 所以 ans[1] = 2

nums[2..4] = [3,2,2] 所以 ans[2] = 2

nums[3..5] = [2,2,1] 所以 ans[3] = 2

nums[4..6] = [2,1,3] 所以 ans[4] = 3

解题思路

class Solution {
    public int[] distinctNumbers(int[] nums, int k) {
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < n; i++) {
            int inKey = nums[i];
            map.put(inKey, map.getOrDefault(inKey, 0) + 1);

            if (i < k - 1) continue;

            ans[i - k + 1] = map.size();

            int outKey = nums[i - k + 1];
            if (map.get(outKey) == 1) {
                map.remove(outKey);
            } else {
                map.put(outKey, map.get(outKey) - 1);
            }
        }
        return ans;
    }
}

1151. 最少交换次数来组合所有的 1

题目描述

给出一个二进制数组 data，你需要通过交换位置，将数组中 任何位置 上的 1 组合到一起，并返回所有可能中所需 最少的交换次数。

示例

输入: data = [1,0,1,0,1]输出: 1解释: 有三种可能的方法可以把所有的 1 组合在一起：[1,1,1,0,0]，交换 1 次；[0,1,1,1,0]，交换 2 次；[0,0,1,1,1]，交换 1 次。所以最少的交换次数为 1。

解题思路

class Solution {
    public int minSwaps(int[] data) {
        int n = data.length;
        // 统计有多少个1
        int k = 0;
        for (int d : data) {
            k += d;
        }
        // 全 0 或只有一个 1, 不需要操作
        if (k == 0 || k == 1) return 0;

        // 问题转化为大小为 k 的窗口中含有0的最少个数
        int sum = 0, maxSum = 0;
        for (int i = 0; i < n; i++) {
            sum += data[i];

            if (i < k - 1) continue;

            maxSum = Math.max(sum, maxSum);
            sum -= data[i - k + 1];
        }
        return k - maxSum;
    }
}

2107. 分享 K 个糖果后独特口味的数量

题目描述

您将获得一个 从0开始的 整数数组 candies ，其中 candies[i] 表示第 i 个糖果的味道。你妈妈想让你和你妹妹分享这些糖果，给她 k 个连续的糖果，但你想保留尽可能多的糖果口味。在与妹妹分享后，返回最多可保留的独特口味的糖果。

示例

输入: candies = [2,2,2,2,3,3], k = 2输出: 2解释:在[3,4]范围内（含[2,3]）的糖果中加入[2,3]口味。你可以吃各种口味的糖果[2,2,2,3]。有两种独特的口味，所以返回2。请注意，你也可以分享口味为[2,2]的糖果，吃口味为[2,2,3,3]的糖果。

解题思路

class Solution {
    public int shareCandies(int[] candies, int k) {
        // 问题转化: 连续 k 个中最少糖果种类数
        int n = candies.length;
        Map<Integer, Integer> total = new HashMap<>();
        for (int candy : candies) {
            total.put(candy, total.getOrDefault(candy, 0) + 1);
        }
        if (k == 0) return total.size();

        int sum = 0, minSum = n;
        Map<Integer, Integer> map = new HashMap<>(total);
        for (int i = 0; i < n; i++) {
            if (map.get(candies[i]) == 1) sum++;
            map.put(candies[i], map.get(candies[i]) - 1);

            if (i < k - 1) continue;

            minSum = Math.min(sum, minSum);

            if (map.get(candies[i - k + 1]) == 0) sum--;
            map.put(candies[i - k + 1], map.get(candies[i - k + 1]) + 1);
        }
        return total.size() - minSum;
    }
}

1989. 捉迷藏中可捕获的最大人数

题目描述

你正在和你的朋友玩捉迷藏游戏。在捉迷藏比赛中，人们被分成两组：是 “鬼” 的人，和不是 “鬼” 的人。是 “鬼” 的人想要抓住尽可能多的不是 “鬼” 的人。

给定一个 从 0 开始建立索引 的整数数组 team，其中只包含 0 (表示不是 “鬼” 的人) 和 1 (表示是 “鬼” 的人)，以及一个整数 dist。索引 i 为 “鬼” 的人可以捕获索引在 [i - dist, i + dist](包括) 范围内且不是 “鬼” 的任何一个人。

返回 “鬼” 所能捕获的最大人数。

示例

输入: team = [0,1,0,1,0], dist = 3输出: 2解释:在索引 1 的 “鬼” 可以捕获范围 [i-dist, i+dist] = [1-3, 1+3] = [-2, 4] 内的人。他们可以抓住索引 2 中不是 “鬼” 的人。在索引 3 的 “鬼” 可以捕获范围 [i-dist, i+dist] = [3-3, 3+3] = [0, 6] 内的人。他们可以抓住索引 0 中不是 “鬼” 的人。在索引 4 上不是 “鬼” 的人不会被抓住，因为在索引 1 和 3 上的人已经抓住了一个人。

解题思路

class Solution {
    public int catchMaximumAmountofPeople(int[] team, int dist) {
        int n = team.length;
        List<Integer> ghosts = new ArrayList<>();
        List<Integer> people = new ArrayList<>();
        // 提取索引
        for (int i = 0; i < n; i++) {
            if (team[i] == 1) ghosts.add(i);
            else people.add(i);
        }

        int ans = 0;
        int i = 0, j = 0;
        while (i < ghosts.size() && j < people.size()) {
            int g = ghosts.get(i);
            int p = people.get(j);
            if (Math.abs(g - p) <= dist) {
                ans++;  // p 在 g 可抓住的范围里
                i++;
                j++;
            } else if (p < g - dist) {
                j++; // 人太靠左，右移
            } else {
                i++; // 鬼太靠左，右移
            }
        }
        return ans;
    }
}

如果觉得文章对你有用，请随意赞赏

滑动窗口

定长滑动窗口 part02

https://pengxiang.space/archives/%E5%AE%9A%E9%95%BF%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%20part02

作者

孤舟未系

发布于

2025/11/05 22:25

更新于

2025/11/05 22:25

许可协议

CC BY 4.0

定长滑动窗口 part02

作者

发布于

更新于

许可协议

评论