标签： 哈希表

目标

给你一个数字数组 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;
    }

}

性能

目标

给你一个字符串 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;
    }
}

性能

目标

给你一个整数数组 arr ，请你将数组中的每个元素替换为它们排序后的序号。

序号代表了一个元素有多大。序号编号的规则如下：

• 序号从 1 开始编号。
• 一个元素越大，那么序号越大。如果两个元素相等，那么它们的序号相同。
• 每个数字的序号都应该尽可能地小。

示例 1：

输入：arr = [40,10,20,30]
输出：[4,1,2,3]
解释：40 是最大的元素。 10 是最小的元素。 20 是第二小的数字。 30 是第三小的数字。

示例 2：

输入：arr = [100,100,100]
输出：[1,1,1]
解释：所有元素有相同的序号。

示例 3：

输入：arr = [37,12,28,9,100,56,80,5,12]
输出：[5,3,4,2,8,6,7,1,3]

说明：

• 0 <= arr.length <= 10^5
• -10^9 <= arr[i] <= 10^9

思路

有一个整数数组 arr，返回每个元素排序后的序号，序号从 1 开始，如果元素值相同那么序号也相同，并且后面的序号无需考虑前面重复的元素，比如 [10 20 20 30]，返回 [1, 2, 2, 3] 而不是 [1, 2, 2, 4]。

排序 arr 的下标数组 index，根据排序后的 index 返填原数组的序号，注意去重即可。

代码

/**
 * @date 2026-07-14 10:11
 */
public class ArrayRankTransform1331 {

    public int[] arrayRankTransform(int[] arr) {
        int n = arr.length;
        Integer[] index = new Integer[n];
        Arrays.setAll(index, i -> i);
        Arrays.sort(index, (a, b) -> (arr[a] - arr[b]));
        int prev = Integer.MIN_VALUE;
        int sort = 0;
        for (int i = 0; i < n; i++) {
            if (prev != arr[index[i]]){
                sort++;
            }
            prev = arr[index[i]];
            arr[index[i]] = sort;
        }
        return arr;
    }

}

性能