哈希表 – shelterofly

目标

给你一个数组 nums，你可以执行以下操作任意次数：

选择相邻元素对中和最小的一对。如果存在多个这样的对，选择最左边的一个。
用它们的和替换这对元素。

返回将数组变为非递减所需的最小操作次数。

如果一个数组中每个元素都大于或等于它前一个元素（如果存在的话），则称该数组为非递减。

示例 1：

输入： nums = [5,2,3,1]
输出： 2
解释：
元素对 (3,1) 的和最小，为 4。替换后 nums = [5,2,4]。
元素对 (2,4) 的和为 6。替换后 nums = [5,6]。
数组 nums 在两次操作后变为非递减。

示例 2：

输入： nums = [1,2,2]
输出： 0
解释：
数组 nums 已经是非递减的。

说明：

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

提示：

We can perform the simulation using data structures.
Maintain an array index and value using a map since we need to find the next and previous ones.
Maintain the indices to be removed using a hash set.
Maintain the neighbor sums with the smaller indices (set or priority queue).
Keep the 3 structures in sync during the removals.

思路

代码

性能

目标

给你一个数组 nums，你可以执行以下操作任意次数：

选择相邻元素对中和最小的一对。如果存在多个这样的对，选择最左边的一个。
用它们的和替换这对元素。

返回将数组变为非递减所需的最小操作次数。

如果一个数组中每个元素都大于或等于它前一个元素（如果存在的话），则称该数组为非递减。

示例 1：

输入： nums = [5,2,3,1]
输出： 2
解释：
元素对 (3,1) 的和最小，为 4。替换后 nums = [5,2,4]。
元素对 (2,4) 的和为 6。替换后 nums = [5,6]。
数组 nums 在两次操作后变为非递减。

示例 2：

输入： nums = [1,2,2]
输出： 0
解释：
数组 nums 已经是非递减的。

说明：

1 <= nums.length <= 50
-1000 <= nums[i] <= 1000

思路

有一个数组 nums，每一次操作可以将数组中和最小的相邻元素用它们的和替换掉，求使得数组非递减所需要的最少操作次数。

暴力解法是每次遍历找到和最小的数对并替换，直到数组非递减。可以使用 next 数组模拟链表来删除元素。

代码


/**
 * @date 2026-01-22 9:02
 */
public class MinimumPairRemoval3507 {

    public int minimumPairRemoval_v1(int[] nums) {
        int res = 0;
        boolean decrease;
        int n = nums.length;
        int[] next = new int[n];
        Arrays.setAll(next, i -> i + 1);
        do {
            decrease = false;
            int index = 0, sum = Integer.MAX_VALUE;
            for (int i = 0; next[i] < n; i = next[i]) {
                if (nums[next[i]] < nums[i]) {
                    decrease = true;
                }
                int s = nums[i] + nums[next[i]];
                if (s < sum) {
                    sum = s;
                    index = i;
                }
            }
            if (decrease) {
                nums[index] = sum;
                next[index] = next[next[index]];
                res++;
            }
        } while (decrease);
        return res;
    }

}

性能

目标

有一个大型的 (m - 1) x (n - 1) 矩形田地，其两个对角分别是 (1, 1) 和 (m, n) ，田地内部有一些水平栅栏和垂直栅栏，分别由数组 hFences 和 vFences 给出。

水平栅栏为坐标 (hFences[i], 1) 到 (hFences[i], n)，垂直栅栏为坐标 (1, vFences[i]) 到 (m, vFences[i]) 。

返回通过移除一些栅栏（可能不移除）所能形成的最大面积的正方形田地的面积，或者如果无法形成正方形田地则返回 -1。

由于答案可能很大，所以请返回结果对 10^9 + 7 取余后的值。

注意：田地外围两个水平栅栏（坐标 (1, 1) 到 (1, n) 和坐标 (m, 1) 到 (m, n) ）以及两个垂直栅栏（坐标 (1, 1) 到 (m, 1) 和坐标 (1, n) 到 (m, n) ）所包围。这些栅栏不能被移除。

示例 1：

输入：m = 4, n = 3, hFences = [2,3], vFences = [2]
输出：4
解释：移除位于 2 的水平栅栏和位于 2 的垂直栅栏将得到一个面积为 4 的正方形田地。

示例 2：

输入：m = 6, n = 7, hFences = [2], vFences = [4]
输出：-1
解释：可以证明无法通过移除栅栏形成正方形田地。

说明：

3 <= m, n <= 10^9
1 <= hFences.length, vFences.length <= 600
1 < hFences[i] < m
1 < vFences[i] < n
hFences 和 vFences 中的元素是唯一的。

思路

有一个 (m - 1) x (n - 1) 矩形田地，左上角坐标为 (1, 1)，右下角坐标为 (m, n)，田地内部有一些栅栏，水平栅栏 i 的纵坐标为 hFences[i]，垂直栅栏 j 的横坐标为 vFences[j]。可以移除一些栅栏，求能够形成的最大正方形的面积。

使用哈希表分别记录水平与垂直方向可能的间隔，找到最大相等间隔，相乘即可。

代码


/**
 * @date 2026-01-16 8:49
 */
public class MaximizeSquareArea2975 {

    public int maximizeSquareArea(int m, int n, int[] hFences, int[] vFences) {
        Set<Integer> hq = getInterval(m, hFences);
        Set<Integer> vq = getInterval(n, vFences);
        hq.retainAll(vq);
        if (hq.size() == 0) {
            return -1;
        }
        long res = 0;
        int mod = 1000000007;
        for (Integer num : hq) {
            res = Math.max(res, num);
        }
        return (int) (res * res % mod);
    }

    private Set<Integer> getInterval(int edge, int[] fences) {
        Arrays.sort(fences);
        Set<Integer> set = new HashSet<>();
        int n = fences.length;
        for (int i = 0; i < n; i++) {
            set.add(fences[i] - 1);
            set.add(edge - fences[i]);
            for (int j = i + 1; j < n; j++) {
                set.add(fences[j] - fences[i]);
            }
        }
        set.add(edge - 1);
        return set;
    }

}

性能

目标

给你一个网格图，由 n + 2 条横线段和 m + 2 条竖线段组成，一开始所有区域均为 1 x 1 的单元格。

所有线段的编号从 1 开始。

给你两个整数 n 和 m 。

同时给你两个整数数组 hBars 和 vBars 。

hBars 包含区间 [2, n + 1] 内互不相同的横线段编号。
vBars 包含 [2, m + 1] 内互不相同的竖线段编号。

如果满足以下条件之一，你可以移除两个数组中的部分线段：

如果移除的是横线段，它必须是 hBars 中的值。
如果移除的是竖线段，它必须是 vBars 中的值。

请你返回移除一些线段后（可能不移除任何线段），剩余网格图中最大正方形空洞的面积，正方形空洞的意思是正方形内部不含有任何线段。

示例 1：

输入：n = 2, m = 1, hBars = [2,3], vBars = [2]
输出：4
解释：左边的图是一开始的网格图。
横线编号的范围是区间 [1,4] ，竖线编号的范围是区间 [1,3] 。
可以移除的横线段为 [2,3] ，竖线段为 [2] 。
一种得到最大正方形面积的方法是移除横线段 2 和竖线段 2 。
操作后得到的网格图如右图所示。
正方形空洞面积为 4。
无法得到面积大于 4 的正方形空洞。
所以答案为 4 。

示例 2：

输入：n = 1, m = 1, hBars = [2], vBars = [2]
输出：4
解释：左边的图是一开始的网格图。
横线编号的范围是区间 [1,3] ，竖线编号的范围是区间 [1,3] 。
可以移除的横线段为 [2] ，竖线段为 [2] 。
一种得到最大正方形面积的方法是移除横线段 2 和竖线段 2 。
操作后得到的网格图如右图所示。
正方形空洞面积为 4。
无法得到面积大于 4 的正方形空洞。
所以答案为 4 。

示例 3：

输入：n = 2, m = 3, hBars = [2,3], vBars = [2,3,4]
输出：9
解释：左边的图是一开始的网格图。
横线编号的范围是区间 [1,4] ，竖线编号的范围是区间 [1,5] 。
可以移除的横线段为 [2,3] ，竖线段为 [2,3,4] 。
一种得到最大正方形面积的方法是移除横线段 2、3 和竖线段 3、4 。
操作后得到的网格图如右图所示。
正方形空洞面积为 9。
无法得到面积大于 9 的正方形空洞。
所以答案为 9 。

说明：

1 <= n <= 10^9
1 <= m <= 10^9
1 <= hBars.length <= 100
2 <= hBars[i] <= n + 1
1 <= vBars.length <= 100
2 <= vBars[i] <= m + 1
hBars 中的值互不相同。
vBars 中的值互不相同。

思路

有一个网格图由 n + 2 条横线段编号为 1 ~ n + 2 和 m + 2 条竖线段编号为 1 ~ m + 2 组成，单元格为 1 x 1，即横线间隔为 1，竖线间隔为 1。有两个数组 hBars 与 vBars，给出了横线段的编号 2 ~ n + 1 与竖线段编号 2 ~ m + 1 内的线段。删除其中的一些线段，使得空洞的正方形面积最大，返回面积的最大值。

要使空洞最大，能删尽删，找出两个数组线段编号连续的长度最大值，取二者的最小值（正方形），加一（删掉 k 条线段，空洞的边长为 k + 1）后平方即可。

代码


/**
 * @date 2026-01-15 9:08
 */
public class MaximizeSquareHoleArea2943 {

    public int maximizeSquareHoleArea(int n, int m, int[] hBars, int[] vBars) {
        Arrays.sort(hBars);
        Arrays.sort(vBars);
        int hmax = getMaxInterval(hBars);
        int vmax = getMaxInterval(vBars);
        int min = Math.min(hmax, vmax) + 1;
        return min * min;
    }

    private int getMaxInterval_v1(int[] bars) {
        int l = bars.length;
        int max = 1;
        int i = 0;
        while (i < l - 1) {
            int start = i;
            do {
                i++;
            } while (i < l && bars[i - 1] + 1 == bars[i]);
            max = Math.max(max, i - start);
        }
        return max;
    }

}

性能

961.在长度2N的数组中找出重复N次的元素

目标

给你一个整数数组 nums ，该数组具有以下属性：

nums.length == 2 * n.
nums 包含 n + 1 个不同的元素
nums 中恰有一个元素重复 n 次

找出并返回重复了 n 次的那个元素。

示例 1：

输入：nums = [1,2,3,3]
输出：3

示例 2：

输入：nums = [2,1,2,5,3,2]
输出：2

示例 3：

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

说明：

2 <= n <= 5000
nums.length == 2 * n
0 <= nums[i] <= 10^4
nums 由 n + 1 个不同的元素组成，且其中一个元素恰好重复 n 次

思路

长度为 2 * n 数组 nums 有 n + 1 个不同元素，其中恰好有一个元素重复 n 次，返回该重复元素。

除了该重复元素，其余元素各不相同。

暴力做法是使用哈希表记录元素的出现次数，如果出现次数大于 1，直接返回，空间复杂度为 O(n)。

对于本题，从下标 1 开始与第一个元素比较，如果相等直接返回。否则问题变成从 2n - 1 个元素中找重复 n 次的元素，重复元素占绝对多数，可以使用摩尔投票算法。

还可以根据重复元素的最小间隔来分析：

假设重复元素至少隔着一个其它元素，有 n - 1 个空隙，至少有 2 * n - 1 个元素，可能。
假设重复元素至少隔着两个其它元素，有 n - 1 个空隙，至少有 n + 2 * (n - 1) = 3 * n - 2 个元素，当 n = 2 时，有可能，当 n > 2 时，必定存在一个重复元素的间隔小于 2，否则元素个数不够。

也就是说，可以检查当前元素与其前 1、2、3 个元素是否相等来找出该重复元素。空间复杂度为 O(1)。

以上算法的时间复杂度均为 O(n)，还有一种期望 O(1) 的算法，使用随机数，随机选取两个元素。它们两个相等的概率是 n/2n × (n - 1)/(2n - 1) = 1/2 * (1 - 1/n)/(2 - 1/n)，当 n = 2 时，p = 1/6，当 n -> ∞，p -> 1/4。期望循环次数 <= 6。

代码


/**
 * @date 2026-01-04 14:45
 */
public class RepeatedNTimes961 {

    public int repeatedNTimes_v1(int[] nums) {
        int n = nums.length;
        int candidate = 0;
        int vote = 0;
        for (int i = 1; i < n; i++) {
            if (nums[i] == nums[0]) {
                return nums[0];
            }
            if (vote == 0) {
                candidate = nums[i];
                vote = 1;
            } else if (candidate != nums[i]) {
                vote--;
            } else {
                return candidate;
            }
        }
        return candidate;
    }

    public int repeatedNTimes(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1] || (i >= 2 && nums[i] == nums[i - 2]) || (i >= 3 && nums[i] == nums[i - 3])) {
                return nums[i];
            }
        }
        return 0;
    }

}

性能

756.金字塔转换矩阵

目标

你正在把积木堆成金字塔。每个块都有一个颜色，用一个字母表示。每一行的块比它下面的行少一个块，并且居中。

为了使金字塔美观，只有特定的三角形图案是允许的。一个三角形的图案由两个块和叠在上面的单个块组成。模式是以三个字母字符串的列表形式 allowed 给出的，其中模式的前两个字符分别表示左右底部块，第三个字符表示顶部块。

例如，"ABC" 表示一个三角形图案，其中一个 “C” 块堆叠在一个 'A' 块(左)和一个 'B' 块(右)之上。请注意，这与 "BAC" 不同，"B" 在左下角，"A" 在右下角。

你从作为单个字符串给出的底部的一排积木 bottom 开始，必须将其作为金字塔的底部。

在给定 bottom 和 allowed 的情况下，如果你能一直构建到金字塔顶部，使金字塔中的每个三角形图案都是在 allowed 中的，则返回 true ，否则返回 false 。

示例 1：

输入：bottom = "BCD", allowed = ["BCC","CDE","CEA","FFF"]
输出：true
解释：允许的三角形图案显示在右边。
从最底层(第 3 层)开始，我们可以在第 2 层构建“CE”，然后在第 1 层构建“E”。
金字塔中有三种三角形图案，分别是 “BCC”、“CDE” 和 “CEA”。都是允许的。

示例 2：

输入：bottom = "AAAA", allowed = ["AAB","AAC","BCD","BBE","DEF"]
输出：false
解释：允许的三角形图案显示在右边。
从最底层(即第 4 层)开始，创造第 3 层有多种方法，但如果尝试所有可能性，你便会在创造第 1 层前陷入困境。

说明：

2 <= bottom.length <= 6
0 <= allowed.length <= 216
allowed[i].length == 3
所有输入字符串中的字母来自集合 {'A', 'B', 'C', 'D', 'E', 'F'}。
allowed 中所有值都是唯一的

思路

有一排积木 bottom，将其作为金字塔的底部，又有一个模式列表 allowed，每个模式是一个长度为 3 的字符串 pattern，表示 pattern[2] 堆叠在左侧的 pattern[0] 和右侧的 pattern[1] 之上。判断能否使用给定的模式堆成一个金字塔。

使用哈希表保存 pattern 下面两个与上面一个的对应关系，dfs 暴力枚举所有可能，分为两个维度，枚举当前层所有可能的排列，生成下一层所有可能的排列；枚举特定的上一层排列生成对应可能的排列。

代码


/**
 * @date 2025-12-29 9:23
 */
public class PyramidTransition756 {

    public boolean pyramidTransition(String bottom, List<String> allowed) {
        int n = bottom.length();
        Map<String, Set<Character>> map = new HashMap<>();
        for (String s : allowed) {
            String key = s.substring(0, 2);
            map.putIfAbsent(key, new HashSet<>());
            map.get(key).add(s.charAt(2));
        }
        Set<String> candidates = new HashSet<>();
        candidates.add(bottom);
        Set<String> top = dfs(1, n, map, candidates);
        return top.size() > 0;
    }

    public Set<String> dfs(int l, int n, Map<String, Set<Character>> map, Set<String> candidates) {
        if (l == n) {
            return candidates;
        }
        Set<String> next = new HashSet<>();
        for (String prev : candidates) {
            Set<String> tmp = new HashSet<>();
            dfs(1, prev, "", map, tmp);
            next.addAll(tmp);
        }
        return dfs(l + 1, n, map, next);
    }

    public void dfs(int index, String prev, String row, Map<String, Set<Character>> map, Set<String> set) {
        if (index == prev.length()) {
            if (!"".equals(row)) {
                set.add(row);
            }
            return;
        }
        String key = prev.charAt(index - 1) + String.valueOf(prev.charAt(index));
        Set<Character> characters = map.get(key);
        if (characters != null) {
            for (Character c : characters) {
                dfs(index + 1, prev, row + c, map, set);
            }
        }
    }

}

性能

2402.会议室III

目标

给你一个整数 n ，共有编号从 0 到 n - 1 的 n 个会议室。

给你一个二维整数数组 meetings ，其中 meetings[i] = [starti, endi] 表示一场会议将会在半闭时间区间 [starti, endi) 举办。所有 starti 的值互不相同。

会议将会按以下方式分配给会议室：

每场会议都会在未占用且编号最小的会议室举办。
如果没有可用的会议室，会议将会延期，直到存在空闲的会议室。延期会议的持续时间和原会议持续时间相同。
当会议室处于未占用状态时，将会优先提供给原开始时间更早的会议。

返回举办最多次会议的房间编号。如果存在多个房间满足此条件，则返回编号最小的房间。

半闭区间 [a, b) 是 a 和 b 之间的区间，包括 a 但不包括 b 。

示例 1：

输入：n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
输出：0
解释：
- 在时间 0 ，两个会议室都未占用，第一场会议在会议室 0 举办。
- 在时间 1 ，只有会议室 1 未占用，第二场会议在会议室 1 举办。
- 在时间 2 ，两个会议室都被占用，第三场会议延期举办。
- 在时间 3 ，两个会议室都被占用，第四场会议延期举办。
- 在时间 5 ，会议室 1 的会议结束。第三场会议在会议室 1 举办，时间周期为 [5,10) 。
- 在时间 10 ，两个会议室的会议都结束。第四场会议在会议室 0 举办，时间周期为 [10,11) 。
会议室 0 和会议室 1 都举办了 2 场会议，所以返回 0 。

示例 2：

输入：n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
输出：1
解释：
- 在时间 1 ，所有三个会议室都未占用，第一场会议在会议室 0 举办。
- 在时间 2 ，会议室 1 和 2 未占用，第二场会议在会议室 1 举办。
- 在时间 3 ，只有会议室 2 未占用，第三场会议在会议室 2 举办。
- 在时间 4 ，所有三个会议室都被占用，第四场会议延期举办。 
- 在时间 5 ，会议室 2 的会议结束。第四场会议在会议室 2 举办，时间周期为 [5,10) 。
- 在时间 6 ，所有三个会议室都被占用，第五场会议延期举办。 
- 在时间 10 ，会议室 1 和 2 的会议结束。第五场会议在会议室 1 举办，时间周期为 [10,12) 。 
会议室 1 和会议室 2 都举办了 2 场会议，所以返回 1 。

说明：

1 <= n <= 100
1 <= meetings.length <= 10^5
meetings[i].length == 2
0 <= starti < endi <= 5 * 10^5
starti 的所有值互不相同

思路

有 n 个会议室，编号为 0 ~ n - 1。有一个二维数组，meetings[i] 表示 [starti, endi) 范围内需要举办一场会议，会优先使用未被占用且编号最小的会议室。如果没有会议室可用，则需要延后举办，如果同一时间有多个会议需要举办，原开始时间最小的优先举办。

这个题目的关键点是，当有多个满足条件的会议室时，选择编号最小的，而不是最早可用的。需要使用两个优先队列，一个追踪会议室的最早空闲时间，另一个则追踪空闲会议室中编号最小的。将会议按照开始时间排序，按顺序遍历，将可选的会议室加入空闲编号堆，如果这个堆非空，从中取一个会议室，并将结束时间（可用时间）放入空闲时间堆中；否则，从空闲时间堆中取一个会议室，将其空闲时间加上会议持续时间后再放入堆中。

代码


/**
 * @date 2025-12-30 14:01
 */
public class MostBooked2402 {

    public int mostBooked(int n, int[][] meetings) {
        int[] cnt = new int[n];
        PriorityQueue<int[]> rooms = new PriorityQueue<>((a, b) -> {
            int compare = a[0] - b[0];
            if (compare != 0) {
                return compare;
            }
            return a[1] - b[1];
        });
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        for (int i = 0; i < n; i++) {
            rooms.offer(new int[]{0, i});
        }
        Arrays.sort(meetings, (a, b) -> a[0] - b[0]);
        for (int[] meeting : meetings) {
            while (!rooms.isEmpty() && rooms.peek()[0] <= meeting[0]) {
                q.offer(rooms.poll());
            }
            int[] room;
            if (!q.isEmpty()) {
                room = q.poll();
                rooms.offer(new int[]{meeting[1], room[1]});
            } else {
                room = rooms.poll();
                rooms.offer(new int[]{room[0] + meeting[1] - meeting[0], room[1]});
            }
            cnt[room[1]]++;
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (cnt[i] > cnt[res]) {
                res = i;
            }
        }
        return res;
    }

}

性能

3583.统计特殊三元组

目标

给你一个整数数组 nums。

特殊三元组定义为满足以下条件的下标三元组 (i, j, k)：

0 <= i < j < k < n，其中 n = nums.length
nums[i] == nums[j] * 2
nums[k] == nums[j] * 2

返回数组中特殊三元组的总数。

由于答案可能非常大，请返回结果对 10^9 + 7 取余数后的值。

示例 1：

输入： nums = [6,3,6]
输出： 1
解释：
唯一的特殊三元组是 (i, j, k) = (0, 1, 2)，其中：
nums[0] = 6, nums[1] = 3, nums[2] = 6
nums[0] = nums[1] * 2 = 3 * 2 = 6
nums[2] = nums[1] * 2 = 3 * 2 = 6

示例 2：

输入： nums = [0,1,0,0]
输出： 1
解释：
唯一的特殊三元组是 (i, j, k) = (0, 2, 3)，其中：
nums[0] = 0, nums[2] = 0, nums[3] = 0
nums[0] = nums[2] * 2 = 0 * 2 = 0
nums[3] = nums[2] * 2 = 0 * 2 = 0

示例 3：

输入： nums = [8,4,2,8,4]
输出： 2
解释：
共有两个特殊三元组：
(i, j, k) = (0, 1, 3)
nums[0] = 8, nums[1] = 4, nums[3] = 8
nums[0] = nums[1] * 2 = 4 * 2 = 8
nums[3] = nums[1] * 2 = 4 * 2 = 8
(i, j, k) = (1, 2, 4)
nums[1] = 4, nums[2] = 2, nums[4] = 4
nums[1] = nums[2] * 2 = 2 * 2 = 4
nums[4] = nums[2] * 2 = 2 * 2 = 4

说明：

3 <= n == nums.length <= 10^5
0 <= nums[i] <= 10^5

思路

找到数组 nums 的三元组 (i, j, k) 满足 nums[i] == nums[k] == 2 * nums[j]，返回特殊三元组的个数。注意这里三元组是元素下标所以不会重复。

枚举右端点，如果为偶数，查找中间元素 nums[k]/2 作为右端点的二元组个数，该二元组 (i, j) 可以同时维护，找到左侧 i 的个数，满足 nums[i] == 2 * nums[j]。

代码


/**
 * @date 2025-12-09 8:55
 */
public class SpecialTriplets3583 {

    public int specialTriplets_v1(int[] nums) {
        int n = nums.length;
        int mod = 1000000007;
        Map<Integer, Long> cnt = new HashMap<>();
        Map<Integer, Long> binaryCnt = new HashMap<>();
        long res = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] % 2 == 0) {
                res += binaryCnt.getOrDefault(nums[i] / 2, 0L);
            }
            binaryCnt.merge(nums[i], cnt.getOrDefault(nums[i] * 2, 0L), Long::sum);
            cnt.merge(nums[i], 1L, Long::sum);
        }
        return (int) (res % mod);
    }

}

性能

1590.使数组和能被P整除

目标

给你一个正整数数组 nums，请你移除最短子数组（可以为空），使得剩余元素的和能被 p 整除。不允许将整个数组都移除。

请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。

子数组定义为原数组中连续的一组元素。

示例 1：

输入：nums = [3,1,4,2], p = 6
输出：1
解释：nums 中元素和为 10，不能被 p 整除。我们可以移除子数组 [4] ，剩余元素的和为 6 。

示例 2：

输入：nums = [6,3,5,2], p = 9
输出：2
解释：我们无法移除任何一个元素使得和被 9 整除，最优方案是移除子数组 [5,2] ，剩余元素为 [6,3]，和为 9 。

示例 3：

输入：nums = [1,2,3], p = 3
输出：0
解释：和恰好为 6 ，已经能被 3 整除了。所以我们不需要移除任何元素。

示例 4：

输入：nums = [1,2,3], p = 7
输出：-1
解释：没有任何方案使得移除子数组后剩余元素的和被 7 整除。

示例 5：

输入：nums = [1000000000,1000000000,1000000000], p = 3
输出：0

说明：

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= p <= 10^9

思路

有一个正整数数组 nums，需要移除一个最短子数组（可以为空），使得剩余元素的和能被 p 整除，返回移除的最短子数组长度，如果无法满足返回 -1。

计算数组和，求出余数 rem，使用哈希表 lastIndex 记录前缀和余数的最大下标，根据当前前缀和的余数，计算需要保留的前缀数组 [0, lastIndex.get((curRem - rem + p) % p)]，计算得到需要减去的子数组 [lastIndex.get((curRem - rem + p) % p) + 1, i] 它的和模 p 余 rem，取长度的最小值即可。

代码


/**
 * @date 2025-11-30 10:41
 */
public class MinSubarray1590 {

    public int minSubarray(int[] nums, int p) {
        int n = nums.length;
        long sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int rem = (int) (sum % p);
        if (rem == 0) {
            return 0;
        }
        Map<Integer, Integer> lastIndex = new HashMap<>();
        lastIndex.putIfAbsent(0, -1);
        int curRem = 0;
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            curRem = (curRem + nums[i]) % p;
            int prev = (p + curRem - rem) % p;
            res = Math.min(res, i - lastIndex.getOrDefault(prev, -n));
            lastIndex.put(curRem, i);
        }
        return res == n ? -1 : res;
    }

}

性能

1015.可被K整除的最小整数

目标

给定正整数 k ，你需要找出可以被 k 整除的、仅包含数字 1 的最小正整数 n 的长度。

返回 n 的长度。如果不存在这样的 n ，就返回-1。

注意： n 可能不符合 64 位带符号整数。

示例 1：

输入：k = 1
输出：1
解释：最小的答案是 n = 1，其长度为 1。

示例 2：

输入：k = 2
输出：-1
解释：不存在可被 2 整除的正整数 n 。

示例 3：

输入：k = 3
输出：3
解释：最小的答案是 n = 111，其长度为 3。

说明：

1 <= k <= 10^5

思路

求仅包含数字 1 且能够整除正整数 k 的数字的最小长度，如不存在返回 -1。

通俗讲就是多长的 11111…… 能够整除 k。为了防止溢出可以只考虑余数，关键是停止条件是什么？如何确定是否存在？

如果余数出现重复，由于计算的式子不变，后续会陷入循环。可以使用哈希表记录出现过的余数。或者循环 k 次，由于余数的范围只可能是 0 ~ k - 1 共 k 个，如果循环 k 次还没有使余数为 0，那么根据鸽巢原理一定存在重复的余数。

代码


/**
 * @date 2025-11-25 9:26
 */
public class SmallestRepunitDivByK1015 {

    public int smallestRepunitDivByK(int k) {
        if (k == 1) {
            return 1;
        }
        int res = 1;
        int num = 1;
        while (res < k) {
            num = (num * 10 + 1) % k;
            res++;
            if (num == 0) {
                return res;
            }
        }
        return -1;
    }
}

2026 年 1 月
一	二	三	四	五	六	日
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31