标签： easy

目标

矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。矩形的上下边平行于 x 轴，左右边平行于 y 轴。

如果相交的面积为 正 ，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。

给出两个矩形 rec1 和 rec2 。如果它们重叠，返回 true；否则，返回 false 。

示例 1：

输入：rec1 = [0,0,2,2], rec2 = [1,1,3,3]
输出：true

示例 2：

输入：rec1 = [0,0,1,1], rec2 = [1,0,2,1]
输出：false

示例 3：

输入：rec1 = [0,0,1,1], rec2 = [2,2,3,3]
输出：false

说明：

• rect1.length == 4
• rect2.length == 4
• -10^9 <= rec1[i], rec2[i] <= 10^9
• rec1 和 rec2 表示一个面积不为零的有效矩形

思路

使用数组 [x1, y1, x2, y2] 表示一个矩形的 左下 (x1, y1) 与 右上 (x2, y2) 顶点。给出两个数组 rec1 与 rec2，判断它们是否重叠。

如果两个矩形重叠，那么两个矩形在两个坐标轴方向的投影区间都应该相交。

代码

/**
 * @date 2026-09-14 9:08
 */
public class IsRectangleOverlap836 {

    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        int x1 = rec1[0], x3 = rec2[0];
        int y1 = rec1[1], y3 = rec2[1];
        int x2 = rec1[2], x4 = rec2[2];
        int y2 = rec1[3], y4 = rec2[3];
        return !(x2 <= x3 || x4 <= x1) && !(y2 <= y3 || y4 <= y1);
    }

}

性能

目标

给你一个数字数组 digits，你需要从中选择三个数字组成一个三位偶数，你的任务是求出 不同 三位偶数的数量。

注意：每个数字在三位偶数中都只能使用 一次 ，并且 不能 有前导零。

示例 1：

输入： digits = [1,2,3,4]
输出： 12
解释： 可以形成的 12 个不同的三位偶数是 124，132，134，142，214，234，312，314，324，342，412 和 432。注意，不能形成 222，因为数字 2 只有一个。

示例 2：

输入： digits = [0,2,2]
输出： 2
解释： 可以形成的三位偶数是 202 和 220。注意，数字 2 可以使用两次，因为数组中有两个 2 。

示例 3：

输入： digits = [6,6,6]
输出： 1
解释： 只能形成 666。

示例 4：

输入： digits = [1,3,5]
输出： 0
解释： 无法形成三位偶数。

说明：

• 3 <= digits.length <= 10
• 0 <= digits[i] <= 9

思路

有一个数字数组 digits，数组元素为 0 ~ 9 ，从中选择 3 个组成一个三位偶数，求不同的三位偶数的个数。

从结果来考虑，三位数 100 ~ 999，针对每个数字判断能否由数组中的数字构成即可。

从构造的角度考虑，需要保证个位是偶数，且百位不是 0，要求数字不同，需要维护可用的数字种类，需要知道每个数字的已使用次数，可以使用回溯。

代码

/**
 * @date 2026-09-11 8:56
 */
public class TotalNumbers3483 {

    public int totalNumbers(int[] digits) {
        int[] d = new int[10];
        for (int num : digits) {
            d[num]++;
        }
        int res = 0;
        for (int num = 100; num < 999; num += 2) {
            if (valid(num, d)) {
                res++;
            }
        }
        return res;
    }

    public boolean valid(int num, int[] d) {
        int[] tmp = new int[10];
        while (num > 0) {
            tmp[num % 10]++;
            num /= 10;
        }
        for (int i = 0; i < 10; i++) {
            if (d[i] < tmp[i]) {
                return false;
            }
        }
        return true;
    }

    public int totalNumbers_v0(int[] digits) {
        int[] d = new int[10];
        for (int num : digits) {
            d[num]++;
        }
        int res = 0;
        // 枚举百位
        for (int i = 1; i < d.length; i++) {
            if (d[i] == 0) {
                continue;
            }
            d[i]--;
            res += dfs(0, i, d);
            d[i]++;
        }

        return res;
    }

    int dfs(int index, int num, int[] d) {
        if (index == 2) {
            // 第三个数如果是偶数返回 1
            return num % 2 == 0 ? 1 : 0;
        }
        int res = 0;
        // 枚举十位
        for (int i = 0; i < d.length; i++) {
            if (d[i] == 0) {
                continue;
            }
            d[i]--;
            res += dfs(index + 1, i, d);
            d[i]++;
        }
        return res;
    }

}

性能

目标

给你一个整数 n。

返回将所有从 [1, n]（包含两端）范围内的整数以 标准 数字格式书写时所用到的 逗号总数。

在 标准 格式中：

• 从右边开始，每 三位 数字后插入一个逗号。
• 位数 少于四位 的数字不包含逗号。

示例 1：

输入： n = 1002
输出： 3
解释：
数字 "1,000"、"1,001" 和 "1,002" 每个都包含一个逗号，总计 3 个逗号。

示例 2：

输入： n = 998
输出： 0
解释：
从 1 到 998 的所有数字位数都少于四位，因此没有使用逗号。

说明：

• 1 <= n <= 10^5

思路

返回 [1, n] 之间所有整数的标准写法中总共有多少逗号。所谓标准写法指从右开始每 3 个数字插入一个逗号，且逗号不能位于开头。

只需判断 1 ~ n 之间有多少个数字在 1,000 ~ 100,000 之间，返回 max(0, n - 999) 即可。

代码

/**
 * @date 2026-09-08 9:04
 */
public class CountCommas3870 {

    public int countCommas(int n) {
        return Math.max(0, n - 999);
    }
}

性能

目标

给你一个长度为 n 的整数数组 nums 和一个整数 k。

对于每个下标 i，定义它的 不稳定值 为 max(nums[0..i]) - min(nums[i..n - 1])。

换句话说：

• max(nums[0..i]) 表示从下标 0 到下标 i 的元素中的 最大值 。
• min(nums[i..n - 1]) 表示从下标 i 到下标 n - 1 的元素中的 最小值 。

如果某个下标 i 的不稳定值 小于等于 k，则称该下标为 稳定下标 。

返回 最小 的稳定下标。如果不存在这样的下标，则返回 -1。

示例 1：

输入： nums = [5,0,1,4], k = 3
输出： 3
解释：
在下标 0 处：[5] 中的最大值是 5，[5, 0, 1, 4] 中的最小值是 0，因此不稳定值为 5 - 0 = 5。
在下标 1 处：[5, 0] 中的最大值是 5，[0, 1, 4] 中的最小值是 0，因此不稳定值为 5 - 0 = 5。
在下标 2 处：[5, 0, 1] 中的最大值是 5，[1, 4] 中的最小值是 1，因此不稳定值为 5 - 1 = 4。
在下标 3 处：[5, 0, 1, 4] 中的最大值是 5，[4] 中的最小值是 4，因此不稳定值为 5 - 4 = 1。
这是第一个不稳定值小于等于 k = 3 的下标，因此答案是 3。

示例 2：

输入： nums = [3,2,1], k = 1
输出： -1
解释：
在下标 0 处，不稳定值为 3 - 1 = 2。
在下标 1 处，不稳定值为 3 - 1 = 2。
在下标 2 处，不稳定值为 3 - 1 = 2。
这些值都不小于等于 k = 1，因此答案是 -1。

示例 3：

输入： nums = [0], k = 0
输出： 0
解释：
在下标 0 处，不稳定值为 0 - 0 = 0，它小于等于 k = 0。因此答案是 0。

说明：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 10^9
• 0 <= k <= 10^9

思路

定义下标 i 的不稳定值为 max(nums[0..i]) - min(nums[i..n - 1])，如果该值小于等于 k 则称 i 为稳定下标。返回最小的稳定下标。

前后缀分解，计算后缀最小值，从左到右枚举，记录前缀最大值，如果满足条件直接返回，否则返回 -1。

代码

/**
 * @date 2026-09-04 9:14
 */
public class FirstStableIndex3903 {

    public int firstStableIndex(int[] nums, int k) {
        int n = nums.length;
        int[] suffix = new int[n + 1];
        Arrays.fill(suffix, Integer.MAX_VALUE);
        for (int i = n - 1; i >= 0; i--) {
            suffix[i] = Math.min(suffix[i + 1], nums[i]);
        }
        int max = 0;
        for (int i = 0; i < n; i++) {
            max = Math.max(max, nums[i]);
            if (max - suffix[i] <= k) {
                return i;
            }
        }
        return -1;
    }

}

性能

目标

给你一个长度为 n 的数组 nums1，其中包含 互不相同 的整数。

你需要构造另一个长度为 n 的数组 nums2，使得 nums2 中的元素要么全部为 奇数，要么全部为 偶数。

对于每个下标 i，你必须从以下两种选择中 任选其一（顺序不限）：

• nums2[i] = nums1[i]
• nums2[i] = nums1[i] - nums1[j]，其中 j != i

如果能够构造出满足条件的数组，则返回 true；否则，返回 false。

示例 1：

输入： nums1 = [2,3]
输出： true
解释：
    选择 nums2[0] = nums1[0] - nums1[1] = 2 - 3 = -1。
    选择 nums2[1] = nums1[1] = 3。
    nums2 = [-1, 3]，两个元素均为奇数。因此答案为 true。

示例 2：

输入： nums1 = [4,6]
输出： true
解释：​​​​​​​
    选择 nums2[0] = nums1[0] = 4。
    选择 nums2[1] = nums1[1] = 6。
    nums2 = [4, 6]，两个元素均为偶数。因此答案为 true。

说明：

• 1 <= n == nums1.length <= 100
• 1 <= nums1[i] <= 100
• nums1 中的所有整数互不相同。

思路

有一个元素互不相同的整数数组 nums1，问能否构造另一个相同长度的数组 nums2，nums2[i] = nums1[i] 或者 nums2[i] = nums1[i] - nums1[j]，其中 j != i。使得 nums2 中的元素全为 奇数 或 偶数。

如果数组元素均为奇数/偶数直接满足条件，否则，可以将偶数减去任意奇数，使得整个数组变为奇数。直接返回 true 即可。

代码

/**
 * @date 2026-09-02 9:17
 */
public class UniformArray3875 {

    public boolean uniformArray(int[] nums1) {
        return true;
    }
}

性能

目标

给你一个字符串 s ，请找出满足每个字符最多出现两次的最长子字符串，并返回该子字符串的 最大 长度。

示例 1：

输入： s = "bcbbbcba"
输出： 4
解释：
以下子字符串长度为 4，并且每个字符最多出现两次："bcbbbcba"。

示例 2：

输入： s = "aaaa"
输出： 2
解释：
以下子字符串长度为 2，并且每个字符最多出现两次："aaaa"。

说明：

• 2 <= s.length <= 100
• s 仅由小写英文字母组成。

思路

返回字符串 s 所有子串中每个字符出现次数不超过两次的最长子串长度。

滑动窗口。

代码

/**
 * @date 2026-08-14 8:44
 */
public class MaximumLengthSubstring3090 {

    public int maximumLengthSubstring(String s) {
        int n = s.length();
        int[] cnt = new int[26];
        int l = 0;
        int res = 0;
        for (int r = 0; r < n; r++) {
            int i = s.charAt(r) - 'a';
            cnt[i]++;
            while (cnt[i] > 2){
                cnt[s.charAt(l++) - 'a']--;
            }
            res = Math.max(res, r - l + 1);
        }
        return res;
    }
}

性能

目标

给你一个下标从 0 开始的整数数组 nums 。

如果一个前缀 nums[0..i] 满足对于 1 <= j <= i 的所有元素都有 nums[j] = nums[j - 1] + 1 ，那么我们称这个前缀是一个 顺序前缀 。特殊情况是，只包含 nums[0] 的前缀也是一个 顺序前缀 。

请你返回 nums 中没有出现过的 最小 整数 x ，满足 x 大于等于 最长 顺序前缀的和。

示例 1：

输入：nums = [1,2,3,2,5]
输出：6
解释：nums 的最长顺序前缀是 [1,2,3] ，和为 6 ，6 不在数组中，所以 6 是大于等于最长顺序前缀和的最小整数。

示例 2：

输入：nums = [3,4,5,1,12,14,13]
输出：15
解释：nums 的最长顺序前缀是 [3,4,5] ，和为 12 ，12、13 和 14 都在数组中，但 15 不在，所以 15 是大于等于最长顺序前缀和的最小整数。

说明：

• 1 <= nums.length <= 50
• 1 <= nums[i] <= 50

思路

定义数组 nums 的顺序前缀是满足 1 <= j <= i, nums[j] = nums[j - 1] + 1 的前缀，返回大于等于数组顺序前缀和且没有出现在数组的最小整数。

使用哈希表保存数组所有元素，计算顺序前缀和 sum，从 sum 返回第一个不在哈希表中的整数即可。

代码

/**
 * @date 2026-08-11 8:58
 */
public class MissingInteger2996 {

    public int missingInteger(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0] + 1;
        }
        Set<Integer> set = Arrays.stream(nums).boxed().collect(Collectors.toSet());
        int sum = nums[0];
        for (int i = 1; i < n; i++) {
            if (nums[i] != nums[i - 1] + 1) {
                break;
            }
            sum += nums[i];
        }
        while (set.contains(sum)) {
            sum++;
        }
        return sum;
    }
}

性能

目标

给你一个整数数组 nums ，数组由若干 互不相同 的整数组成。

数组 nums 原本包含了某个范围内的 所有整数 。但现在，其中可能 缺失 部分整数。

该范围内的 最小 整数和 最大 整数仍然存在于 nums 中。

返回一个 有序 列表，包含该范围内缺失的所有整数，并 按从小到大排序。如果没有缺失的整数，返回一个 空 列表。

示例 1：

输入： nums = [1,4,2,5]
输出： [3]
解释：
最小整数为 1，最大整数为 5，因此完整的范围应为 [1,2,3,4,5]。其中只有 3 缺失。

示例 2：

输入： nums = [7,8,6,9]
输出： []
解释：
最小整数为 6，最大整数为 9，因此完整的范围为 [6,7,8,9]。所有整数均已存在，因此没有缺失的整数。

示例 3：

输入： nums = [5,1]
输出： [2,3,4]
解释：
最小整数为 1，最大整数为 5，因此完整的范围应为 [1,2,3,4,5]。缺失的整数为 2、3 和 4。

说明：

• 2 <= nums.length <= 100
• 1 <= nums[i] <= 100

思路

有一个元素互不相同的数组，原本包含了 [min, max] 之间的所有整数，现在缺失了 (min, max) 中的一些元素，找到并返回缺失的元素。

首先找到数组的 min 与 max，将元素放入哈希表，遍历 (min, max) 判断数字是否在集合中。

代码

/**
 * @date 2026-08-04 8:49
 */
public class FindMissingElements3731 {

    public List<Integer> findMissingElements(int[] nums) {
        int min = 101, max = 0;
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
            set.add(num);
        }
        List<Integer> res = new ArrayList<>();
        for (int i = min + 1; i < max; i++) {
            if (!set.contains(i)) {
                res.add(i);
            }
        }
        return res;
    }
}

性能

目标

给你一个字符串 word，由 不同 小写英文字母组成。

电话键盘上的按键与 不同 小写英文字母集合相映射，可以通过按压按键来组成单词。例如，按键 2 对应 ["a","b","c"]，我们需要按一次键来输入 "a"，按两次键来输入 "b"，按三次键来输入 "c"。

现在允许你将编号为 2 到 9 的按键重新映射到 不同 字母集合。每个按键可以映射到 任意数量 的字母，但每个字母 必须 恰好 映射到 一个 按键上。你需要找到输入字符串 word 所需的 最少 按键次数。

返回重新映射按键后输入 word 所需的 最少 按键次数。

下面给出了一种电话键盘上字母到按键的映射作为示例。注意 1，*，# 和 0 不 对应任何字母。

示例 1：

输入：word = "abcde"
输出：5
解释：图片中给出的重新映射方案的输入成本最小。
"a" -> 在按键 2 上按一次
"b" -> 在按键 3 上按一次
"c" -> 在按键 4 上按一次
"d" -> 在按键 5 上按一次
"e" -> 在按键 6 上按一次
总成本为 1 + 1 + 1 + 1 + 1 = 5 。
可以证明不存在其他成本更低的映射方案。

示例 2：

输入：word = "xycdefghij"
输出：12
解释：图片中给出的重新映射方案的输入成本最小。
"x" -> 在按键 2 上按一次
"y" -> 在按键 2 上按两次
"c" -> 在按键 3 上按一次
"d" -> 在按键 3 上按两次
"e" -> 在按键 4 上按一次
"f" -> 在按键 5 上按一次
"g" -> 在按键 6 上按一次
"h" -> 在按键 7 上按一次
"i" -> 在按键 8 上按一次
"j" -> 在按键 9 上按一次
总成本为 1 + 2 + 1 + 2 + 1 + 1 + 1 + 1 + 1 + 1 = 12 。
可以证明不存在其他成本更低的映射方案。

说明：

• 1 <= word.length <= 26
• word 仅由小写英文字母组成。
• word 中的所有字母互不相同。

思路

可以将 26 个字母映射到 2 ~ 9 按键上，比如将 abc 映射到 2，那么输入 b 需要按两下 2，输入 c 需要按三下 2。给定一个由 不同字母 组成的单词 word，返回输入该字符所需的最少按键次数。

字母出现的频次都是 1，先将所有按键的第一个位置填满，然后是第二个、第三个。

录入单词所需的按键次数为 8 * (1 + 2 + …… + k) + (n % 8) * (k + 1) = 8 * (1 + k) * k / 2 + (n % 8) * (k + 1) = 4 * k * (k + 1) + (n % 8) * (k + 1) = (4 * k + n % 8) * (k + 1)。

代码

/**
 * @date 2026-07-30 9:10
 */
public class MinimumPushes3014 {

    public int minimumPushes_v1(String word) {
        int n = word.length();
        int k = n / 8;
        return (4 * k + n % 8) * (k + 1);
    }
}

性能

目标

给你一个整数数组 nums，请你选择数组的两个不同下标 i 和 j，使 (nums[i]-1)*(nums[j]-1) 取得最大值。

请你计算并返回该式的最大值。

示例 1：

输入：nums = [3,4,5,2]
输出：12 
解释：如果选择下标 i=1 和 j=2（下标从 0 开始），则可以获得最大值，(nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12 。 

示例 2：

输入：nums = [1,5,4,5]
输出：16
解释：选择下标 i=1 和 j=3（下标从 0 开始），则可以获得最大值 (5-1)*(5-1) = 16 。

示例 3：

输入：nums = [3,7]
输出：12

说明：

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

思路

从数组中取两个不同下标的元素相乘并返回最大的乘积。

找到数组最大的两个元素相乘即可。

代码

/**
 * @date 2026-07-27 8:55
 */
public class MaxProduct1464 {

    public int maxProduct(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        return (nums[n - 1] - 1) * (nums[n - 2] - 1);
    }
}

性能