标签： medium

目标

给你一个正整数数组 nums ，请你从中删除一个含有 若干不同元素 的子数组。删除子数组的 得分 就是子数组各元素之 和 。

返回 只删除一个 子数组可获得的 最大得分 。

如果数组 b 是数组 a 的一个连续子序列，即如果它等于 a[l],a[l+1],...,a[r] ，那么它就是 a 的一个子数组。

示例 1：

输入：nums = [4,2,4,5,6]
输出：17
解释：最优子数组是 [2,4,5,6]

示例 2：

输入：nums = [5,2,1,2,5,2,1,2,5]
输出：8
解释：最优子数组是 [5,2,1] 或 [1,2,5]

说明：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^4

思路

有一个正整数数组 nums，求一个不含重复元素的子数组，使得子数组的元素和最大。

滑动窗口，要求窗口内部不含重复元素，求窗口内元素和的最大值。

代码

/**
 * @date 2025-07-22 8:50
 */
public class MaximumUniqueSubarray1695 {

    public int maximumUniqueSubarray(int[] nums) {
        int n = nums.length;
        Set<Integer> set = new HashSet<>();
        int l = 0;
        int sum = 0;
        int res = 0;
        for (int r = 0; r < n; r++) {
            sum += nums[r];
            while (l < r && set.contains(nums[r])) {
                sum -= nums[l];
                set.remove(nums[l++]);
            }
            set.add(nums[r]);
            res = Math.max(res, sum);
        }
        return res;
    }

}

性能

目标

你是一位系统管理员，手里有一份文件夹列表 folder，你的任务是要删除该列表中的所有 子文件夹，并以 任意顺序 返回剩下的文件夹。

如果文件夹 folder[i] 位于另一个文件夹 folder[j] 下，那么 folder[i] 就是 folder[j] 的 子文件夹 。folder[j] 的子文件夹必须以 folder[j] 开头，后跟一个 "/"。例如，"/a/b" 是 "/a" 的一个子文件夹，但 "/b" 不是 "/a/b/c" 的一个子文件夹。

文件夹的「路径」是由一个或多个按以下格式串联形成的字符串：'/' 后跟一个或者多个小写英文字母。

• 例如，"/leetcode" 和 "/leetcode/problems" 都是有效的路径，而空字符串和 "/" 不是。

示例 1：

输入：folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
输出：["/a","/c/d","/c/f"]
解释："/a/b" 是 "/a" 的子文件夹，而 "/c/d/e" 是 "/c/d" 的子文件夹。

示例 2：

输入：folder = ["/a","/a/b/c","/a/b/d"]
输出：["/a"]
解释：文件夹 "/a/b/c" 和 "/a/b/d" 都会被删除，因为它们都是 "/a" 的子文件夹。

示例 3：

输入: folder = ["/a/b/c","/a/b/ca","/a/b/d"]
输出: ["/a/b/c","/a/b/ca","/a/b/d"]

说明：

• 1 <= folder.length <= 4 * 10^4
• 2 <= folder[i].length <= 100
• folder[i] 只包含小写字母和 '/'
• folder[i] 总是以字符 '/' 起始
• folder 每个元素都是 唯一 的

思路

有一个文件夹列表，删除其中所有的子文件夹。

将文件夹列表排序，父目录总是会先出现，记为 prev，使用 startsWith 判断当前目录是否是子目录，如果不是更新 prev，并加入结果集合，否则直接跳过。需要注意 prev 需要以 / 结尾，否则会错误地匹配，比如 /a/b/c 并不是 /a/b/ca 的父目录。

也可以使用字典树来解决该问题，构造字典树，将最后一个节点标记为文件夹列表的下标，dfs 字典树，如果遇到标记非空则直接返回，不再查找子文件夹。

代码

/**
 * @date 2025-07-19 10:57
 */
public class RemoveSubfolders1233 {

    public List<String> removeSubfolders(String[] folder) {
        Arrays.sort(folder);
        String prev = ".";
        List<String> res = new ArrayList<>();
        for (String path : folder) {
            if (path.startsWith(prev)) {
                continue;
            }
            res.add(path);
            prev = path + "/";
        }
        return res;
    }

}

性能

目标

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

nums 的一个 子序列 sub 的长度为 x ，如果其满足以下条件，则称其为 有效子序列 ：

• (sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == ... == (sub[x - 2] + sub[x - 1]) % k

返回 nums 的 最长有效子序列 的长度。

示例 1：

输入：nums = [1,2,3,4,5], k = 2
输出：5
解释：
最长有效子序列是 [1, 2, 3, 4, 5] 。

示例 2：

输入：nums = [1,4,2,3,1,4], k = 3
输出：4
解释：
最长有效子序列是 [1, 4, 1, 4] 。

说明：

• 2 <= nums.length <= 10^3
• 1 <= nums[i] <= 10^7
• 1 <= k <= 10^3

思路

找出数组 nums 的有效子序列的最大长度，有效子序列指相邻元素之和模 k 的值相等。

3201.找出有效子序列的最大长度I 是本题 k = 2 的特例。这个题目可能的组合有 k^2 种。

定义 dp[i][j] 表示子序列后两项模 k 的值为 i 和 j 的子序列长度。

代码

/**
 * @date 2025-07-16 10:18
 */
public class MaximumLength3202 {

    public int maximumLength(int[] nums, int k) {
        int[][] dp = new int[k][k];
        int res = 0;
        for (int num : nums) {
            int m = num % k;
            for (int i = 0; i < k; i++) {
                dp[i][m] = dp[m][i] + 1;
                res = Math.max(res, dp[i][m]);
            }
        }
        return res;
    }

}

性能

目标

给你一个整数数组 nums。

nums 的子序列 sub 的长度为 x ，如果其满足以下条件，则称其为 有效子序列：

• (sub[0] + sub[1]) % 2 == (sub[1] + sub[2]) % 2 == ... == (sub[x - 2] + sub[x - 1]) % 2

返回 nums 的 最长的有效子序列 的长度。

一个 子序列 指的是从原数组中删除一些元素（也可以不删除任何元素），剩余元素保持原来顺序组成的新数组。

示例 1：

输入： nums = [1,2,3,4]
输出： 4
解释：
最长的有效子序列是 [1, 2, 3, 4]。

示例 2：

输入： nums = [1,2,1,1,2,1,2]
输出： 6
解释：
最长的有效子序列是 [1, 2, 1, 2, 1, 2]。

示例 3：

输入： nums = [1,3]
输出： 2
解释：
最长的有效子序列是 [1, 3]。

说明：

• 2 <= nums.length <= 2 * 10^5
• 1 <= nums[i] <= 10^7

思路

找出有效子序列的最大长度，使得子序列中相邻元素和的奇偶性相同。

注意到有效子序列中奇数下标的奇偶性必须相同，同时偶数下标的奇偶性也必须相同。总共四种情况：奇偶、奇奇、偶奇、偶偶。

代码

/**
 * @date 2025-07-16 8:43
 */
public class MaximumLength3201 {

    public int maximumLength(int[] nums) {
        int res = 0;
        for (int a = 0; a <= 1; a++) {
            for (int b = 0; b <= 1; b++) {
                int l = 0;
                int[] p = new int[]{a, b};
                int k = 0;
                for (int num : nums) {
                    if (num % 2 == p[k]) {
                        l++;
                        k ^= 1;
                    }
                }
                res = Math.max(l, res);
            }
        }
        return res;
    }

}

性能

目标

给你一个下标从 0 开始的整数数组 players ，其中 players[i] 表示第 i 名运动员的 能力 值，同时给你一个下标从 0 开始的整数数组 trainers ，其中 trainers[j] 表示第 j 名训练师的 训练能力值 。

如果第 i 名运动员的能力值 小于等于 第 j 名训练师的能力值，那么第 i 名运动员可以 匹配 第 j 名训练师。除此以外，每名运动员至多可以匹配一位训练师，每位训练师最多可以匹配一位运动员。

请你返回满足上述要求 players 和 trainers 的 最大 匹配数。

示例 1：

输入：players = [4,7,9], trainers = [8,2,5,8]
输出：2
解释：
得到两个匹配的一种方案是：
- players[0] 与 trainers[0] 匹配，因为 4 <= 8 。
- players[1] 与 trainers[3] 匹配，因为 7 <= 8 。
可以证明 2 是可以形成的最大匹配数。

示例 2：

输入：players = [1,1,1], trainers = [10]
输出：1
解释：
训练师可以匹配所有 3 个运动员
每个运动员至多只能匹配一个训练师，所以最大答案是 1 。

说明：

• 1 <= players.length, trainers.length <= 10^5
• 1 <= players[i], trainers[j] <= 10^9

思路

有两个数组 arr1 与 arr2，如果 arr1[i] <= arr2[j]，则称 arr1[i] 与 arr2[j] 相匹配。arr1 中的元素最多只能匹配一个 arr2 中的元素，同时，arr2 中的元素最多只能匹配一个 arr1 中的元素，求最大匹配数。

贪心策略，arr1 中的最小元素优先匹配 arr2 中的最小元素。

代码

/**
 * @date 2025-07-13 20:20
 */
public class MatchPlayersAndTrainers2410 {

    public int matchPlayersAndTrainers(int[] players, int[] trainers) {
        Arrays.sort(players);
        Arrays.sort(trainers);
        int m = players.length;
        int n = trainers.length;
        int res = 0;
        int i = 0, j = 0;
        while (i < m && j < n) {
            if (players[i] <= trainers[j]) {
                res++;
                i++;
            }
            j++;
        }
        return res;
    }

}

性能

目标

给你一个正整数 days，表示员工可工作的总天数（从第 1 天开始）。另给你一个二维数组 meetings，长度为 n，其中 meetings[i] = [start_i, end_i] 表示第 i 次会议的开始和结束天数（包含首尾）。

返回员工可工作且没有安排会议的天数。

注意：会议时间可能会有重叠。

示例 1：

输入：days = 10, meetings = [[5,7],[1,3],[9,10]]
输出：2
解释：
第 4 天和第 8 天没有安排会议。

示例 2：

输入：days = 5, meetings = [[2,4],[1,3]]
输出：1
解释：
第 5 天没有安排会议。

示例 3：

输入：days = 6, meetings = [[1,6]]
输出：0
解释：
所有工作日都安排了会议。

说明：

• 1 <= days <= 10^9
• 1 <= meetings.length <= 10^5
• meetings[i].length == 2
• 1 <= meetings[i][0] <= meetings[i][1] <= days

思路

在区间 [1, days] 上有一些区间 [si, ei]，求没有被这些区间覆盖的正整数个数。

将区间按起点排序，记录已访问区间的最大终点 prevEnd，si - prevEnd - 1 即为当前区间与上一个区间之间的整数个数。注意特殊处理开头与结尾。

网友题解则是合并相交的区间，用总数减去区间覆盖的整数即为答案。

代码

/**
 * @date 2025-07-11 18:53
 */
public class CountDays3169 {

    public int countDays(int days, int[][] meetings) {
        Arrays.sort(meetings, (a, b) -> a[0] - b[0]);
        int res = 0;
        int prevEnd = 0;
        for (int[] meeting : meetings) {
            int interval = meeting[0] - prevEnd - 1;
            res += Math.max(interval, 0);
            prevEnd = Math.max(prevEnd, meeting[1]);
        }
        return res + Math.max(0, days - prevEnd);
    }

}

性能

目标

给你一个整数 eventTime 表示一个活动的总时长，这个活动开始于 t = 0 ，结束于 t = eventTime 。

同时给你两个长度为 n 的整数数组 startTime 和 endTime 。它们表示这次活动中 n 个时间 没有重叠 的会议，其中第 i 个会议的时间为 [startTime[i], endTime[i]] 。

你可以重新安排 至多 一个会议，安排的规则是将会议时间平移，且保持原来的 会议时长 ，你的目的是移动会议后 最大化 相邻两个会议之间的 最长 连续空余时间。

请你返回重新安排会议以后，可以得到的 最大 空余时间。

注意，会议 不能 安排到整个活动的时间以外，且会议之间需要保持互不重叠。

注意：重新安排会议以后，会议之间的顺序可以发生改变。

示例 1：

输入：eventTime = 5, startTime = [1,3], endTime = [2,5]
输出：2
解释：
将 [1, 2] 的会议安排到 [2, 3] ，得到空余时间 [0, 2] 。

示例 2：

输入：eventTime = 10, startTime = [0,7,9], endTime = [1,8,10]
输出：7
解释：
将 [0, 1] 的会议安排到 [8, 9] ，得到空余时间 [0, 7] 。

示例 3：

输入：eventTime = 10, startTime = [0,3,7,9], endTime = [1,4,8,10]
输出：6
解释：
将 [3, 4] 的会议安排到 [8, 9] ，得到空余时间 [1, 7] 。

示例 4：

输入：eventTime = 5, startTime = [0,1,2,3,4], endTime = [1,2,3,4,5]
输出：0
解释：
活动中的所有时间都被会议安排满了。

说明：

• 1 <= eventTime <= 10^9
• n == startTime.length == endTime.length
• 2 <= n <= 10^5
• 0 <= startTime[i] < endTime[i] <= eventTime
• endTime[i] <= startTime[i + 1] 其中 i 在范围 [0, n - 2] 之间。

思路

有一个活动有 n 个时间不重叠的会议，重新安排 1 个会议议程，使得空余时间最大。

与 3439.重新安排会议得到最多空余时间I 相比，本题只能重新安排一个会议，但是允许打乱原有的会议顺序。

对于当前会议，如果除了其左右两侧的空余位置之外存在空余位置大于会议时间，那么空余时间是其左右两侧的空余时间加上会议时间。否则，可以将会议左移或者右移到边界，空余时间为左右空余时间之和。

因此可以求出前三大的空余时间，如果会议时间小于等于第三大的空余时间，说明总是可以移到左右空余之外。否则就需要判断当前空余时间是否大于第二、第一大的空余时间，以及是否恰好是其左右空余。

代码

/**
 * @date 2025-07-10 22:15
 */
public class MaxFreeTime3440 {

    public int maxFreeTime(int eventTime, int[] startTime, int[] endTime) {
        int n = startTime.length;
        int[] gap = new int[n + 1];
        int[] intervals = new int[n];
        Arrays.setAll(intervals, i -> endTime[i] - startTime[i]);
        int[] a = new int[]{0, 0};
        int[] b = new int[]{0, 0};
        int[] c = new int[]{0, 0};
        for (int i = 0; i <= n; i++) {
            if (i == 0) {
                gap[i] = startTime[i];
            } else if (i == n) {
                gap[i] = eventTime - endTime[i - 1];
            } else {
                gap[i] = startTime[i] - endTime[i - 1];
            }
            if (gap[i] >= a[0]) {
                c = b;
                b = a;
                a = new int[]{gap[i], i};
            } else if (gap[i] >= b[0]) {
                c = b;
                b = new int[]{gap[i], i};
            } else if (gap[i] >= c[0]) {
                c = new int[]{gap[i], i};
            }
        }
        int res = a[0];
        for (int i = 0; i < n; i++) {
            int g = gap[i] + gap[i + 1];
            if (intervals[i] > a[0]) {
                res = Math.max(res, g);
            } else if (intervals[i] <= c[0]) {
                res = Math.max(res, g + intervals[i]);
            } else if (intervals[i] <= b[0] && (b[1] != i && b[1] != i + 1)) {
                res = Math.max(res, g + intervals[i]);
            } else if (a[1] != i && a[1] != i + 1) {
                res = Math.max(res, g + intervals[i]);
            } else {
                res = Math.max(res, g);
            }
        }
        return res;
    }

}

性能

目标

给你一个整数 eventTime 表示一个活动的总时长，这个活动开始于 t = 0 ，结束于 t = eventTime 。

同时给你两个长度为 n 的整数数组 startTime 和 endTime 。它们表示这次活动中 n 个时间 没有重叠 的会议，其中第 i 个会议的时间为 [startTime[i], endTime[i]] 。

你可以重新安排 至多 k 个会议，安排的规则是将会议时间平移，且保持原来的 会议时长 ，你的目的是移动会议后 最大化 相邻两个会议之间的 最长 连续空余时间。

移动前后所有会议之间的 相对 顺序需要保持不变，而且会议时间也需要保持互不重叠。

请你返回重新安排会议以后，可以得到的 最大 空余时间。

注意，会议 不能 安排到整个活动的时间以外。

示例 1：

输入：eventTime = 5, k = 1, startTime = [1,3], endTime = [2,5]
输出：2
解释：
将 [1, 2] 的会议安排到 [2, 3] ，得到空余时间 [0, 2] 。

示例 2：

输入：eventTime = 10, k = 1, startTime = [0,2,9], endTime = [1,4,10]
输出：6
解释：
将 [2, 4] 的会议安排到 [1, 3] ，得到空余时间 [3, 9] 。

示例 3：

输入：eventTime = 5, k = 2, startTime = [0,1,2,3,4], endTime = [1,2,3,4,5]
输出：0
解释：
活动中的所有时间都被会议安排满了。

说明：

• 1 <= eventTime <= 10^9
• n == startTime.length == endTime.length
• 2 <= n <= 10^5
• 1 <= k <= n
• 0 <= startTime[i] < endTime[i] <= eventTime
• endTime[i] <= startTime[i + 1] 其中 i 在范围 [0, n - 2] 之间。

思路

有一个活动有 n 个时间不重叠的会议，重新安排 k 个会议议程，使得空余时间最大。

先根据会议时间排序，滑动窗口计算 k 个会议的总时间，以及 [end[l - 1], start[r + 1]]，相减即为窗口内的最大空余时间。

代码

/**
 * @date 2025-07-09 8:52
 */
public class MaxFreeTime3439 {

    public int maxFreeTime(int eventTime, int k, int[] startTime, int[] endTime) {
        int n = startTime.length;
        int[][] interval = new int[n + 2][2];
        interval[0][1] = 0;
        for (int i = 1; i <= n; i++) {
            interval[i] = new int[]{startTime[i - 1], endTime[i - 1]};
        }
        interval[n + 1][0] = eventTime;
        int l = 1;
        int res = 0, sum = 0;
        for (int r = 1; r <= n; r++) {
            sum += interval[r][1] - interval[r][0];
            if (r - l == k - 1) {
                res = Math.max(res, interval[r + 1][0] - interval[l - 1][1] - sum);
                sum -= interval[l][1] - interval[l][0];
                l++;
            }
        }
        return res;
    }

}

性能

目标

给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。

你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。在任意一天 d 中只能参加一场会议。

请你返回你可以参加的 最大 会议数目。

示例 1：

输入：events = [[1,2],[2,3],[3,4]]
输出：3
解释：你可以参加所有的三个会议。
安排会议的一种方案如上图。
第 1 天参加第一个会议。
第 2 天参加第二个会议。
第 3 天参加第三个会议。

示例 2：

输入：events= [[1,2],[2,3],[3,4],[1,2]]
输出：4

说明：​​​​​​

• 1 <= events.length <= 10^5
• events[i].length == 2
• 1 <= startDayi <= endDayi <= 10^5

思路

二维数组 events 表示会议的开始与结束时间，每天最多参加一次会议求最多可以参加几个会议。

按开始时间分组，记录结束时间列表，优先参加结束时间最小的会议。遍历每一天，去掉过期的会议结束时间，将当前的结束时间列表加入优先队列，取最小的结束时间，如果大于等于开始时间则计入答案。

代码

/**
 * @date 2025-07-07 9:07
 */
public class MaxEvents1353 {

    public int maxEvents(int[][] events) {
        int max = 0;
        for (int[] event : events) {
            max = Math.max(max, event[1]);
        }
        List<Integer>[] groups = new List[max + 1];
        Arrays.setAll(groups, x -> new ArrayList<>());
        for (int[] event : events) {
            groups[event[0]].add(event[1]);
        }
        PriorityQueue<Integer> q = new PriorityQueue<>();
        int res = 0;
        for (int i = 1; i <= max; i++) {
            while (!q.isEmpty() && q.peek() < i) {
                q.poll();
            }
            q.addAll(groups[i]);
            if (!q.isEmpty()) {
                res++;
                q.poll();
            }
        }
        return res;
    }

}

性能

目标

给你两个整数数组 nums1 和 nums2 ，请你实现一个支持下述两类查询的数据结构：

1. 累加 ，将一个正整数加到 nums2 中指定下标对应元素上。
2. 计数 ，统计满足 nums1[i] + nums2[j] 等于指定值的下标对 (i, j) 数目（0 <= i < nums1.length 且 0 <= j < nums2.length）。

实现 FindSumPairs 类：

• FindSumPairs(int[] nums1, int[] nums2) 使用整数数组 nums1 和 nums2 初始化 FindSumPairs 对象。
• void add(int index, int val) 将 val 加到 nums2[index] 上，即，执行 nums2[index] += val 。
• int count(int tot) 返回满足 nums1[i] + nums2[j] == tot 的下标对 (i, j) 数目。

示例：

输入：
["FindSumPairs", "count", "add", "count", "count", "add", "add", "count"]
[[[1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]], [7], [3, 2], [8], [4], [0, 1], [1, 1], [7]]
输出：
[null, 8, null, 2, 1, null, null, 11]
解释：
FindSumPairs findSumPairs = new FindSumPairs([1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]);
findSumPairs.count(7);  // 返回 8 ; 下标对 (2,2), (3,2), (4,2), (2,4), (3,4), (4,4) 满足 2 + 5 = 7 ，下标对 (5,1), (5,5) 满足 3 + 4 = 7
findSumPairs.add(3, 2); // 此时 nums2 = [1,4,5,4,5,4]
findSumPairs.count(8);  // 返回 2 ；下标对 (5,2), (5,4) 满足 3 + 5 = 8
findSumPairs.count(4);  // 返回 1 ；下标对 (5,0) 满足 3 + 1 = 4
findSumPairs.add(0, 1); // 此时 nums2 = [2,4,5,4,5,4]
findSumPairs.add(1, 1); // 此时 nums2 = [2,5,5,4,5,4]
findSumPairs.count(7);  // 返回 11 ；下标对 (2,1), (2,2), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,4) 满足 2 + 5 = 7 ，下标对 (5,3), (5,5) 满足 3 + 4 = 7

说明：

• 1 <= nums1.length <= 1000
• 1 <= nums2.length <= 10^5
• 1 <= nums1[i] <= 10^9
• 1 <= nums2[i] <= 10^5
• 0 <= index < nums2.length
• 1 <= val <= 10^5
• 1 <= tot <= 10^9
• 最多调用 add 和 count 函数各 1000 次

思路

统计元素出现次数，针对每一个 count 操作，遍历 cnt1，累加 cnt1.get(x) * cnt2.get(tot - x) 即可。

代码

/**
 * @date 2025-07-06 16:48
 */
public class FindSumPairs1865 {

    class FindSumPairs {

        int[] nums1;
        int[] nums2;
        Map<Integer, Integer> cnt1 = new HashMap<>();
        Map<Integer, Integer> cnt2 = new HashMap<>();

        public FindSumPairs(int[] nums1, int[] nums2) {
            this.nums1 = nums1;
            this.nums2 = nums2;
            for (int num : nums1) {
                cnt1.merge(num, 1, Integer::sum);
            }
            for (int num : nums2) {
                cnt2.merge(num, 1, Integer::sum);

            }
        }

        public void add(int index, int val) {
            int key = nums2[index];
            cnt2.merge(key, -1, Integer::sum);
            if (cnt2.get(key) <= 0) {
                cnt2.remove(key);
            }
            nums2[index] += val;
            cnt2.merge(key + val, 1, Integer::sum);
        }

        public int count(int tot) {
            int res = 0;
            for (Map.Entry<Integer, Integer> entry : cnt1.entrySet()) {
                int key = entry.getKey();
                int value = entry.getValue();
                res += value * cnt2.getOrDefault(tot - key, 0);
            }
            return res;
        }
    }
}

性能