What is the main strategy for Make Sum Divisible by P?

Use prefix sums combined with a hash map to track remainders modulo p, allowing efficient identification of minimal subarrays to remove.

Can the entire array be removed to satisfy divisibility?

No, the problem explicitly forbids removing the entire array; at least one element must remain.

How do I handle cases where the array sum is already divisible by p?

Return 0 immediately since no subarray removal is necessary when the total sum modulo p is zero.

What is the time complexity of this approach?

The solution runs in O(n) time, scanning the array once and using a hash map for constant-time remainder lookups.

Are there pitfalls with large numbers in nums or p?

Yes, always compute prefix sums modulo p to avoid integer overflow and ensure correct subarray remainder calculations.

#1590

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

使数组和能被 P 整除

给你一个正整数数组 nums ，请你移除最短子数组（可以为空），使得剩余元素的和能被 p 整除。不允许将整个数组都移除。请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。子数组定义为原数组中连续的一组元素。示例 1：输入： nums = [3,1,4…

数组哈希表前缀和

题目描述

给你一个正整数数组 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⁵
1 <= nums[i] <= 10⁹
1 <= p <= 10⁹

lightbulb

解题思路

方法一：前缀和 + 哈希表

我们可以先求出数组 $\textit{nums}$ 所有元素之和模 $p$ 的值，记为 $k$ 。如果 $k$ 为 $0$ ，说明数组 $\textit{nums}$ 所有元素之和就是 $p$ 的倍数，直接返回 $0$ 即可。

如果 $k$ 不为 $0$ ，我们需要找到一个最短的子数组，使得删除该子数组后，剩余元素之和模 $p$ 的值为 $0$ 。

我们可以遍历数组 $\textit{nums}$ ，维护当前的前缀和模 $p$ 的值，记为 $cur$ 。用哈希表 $last$ 记录每个前缀和模 $p$ 的值最后一次出现的位置。

如果当前存在一个以 $\textit{nums}[i]$ 结尾的子数组，使得删除该子数组后，剩余元素之和模 $p$ 的值为 $0$ 。也就是说，我们需要找到此前的一个前缀和模 $p$ 的值为 $target$ 的位置 $j$ ，使得 $(target + k - cur) \bmod p = 0$ 。如果找到，我们就可以将 $j + 1$ 到 $i$ 这一段闭区间子数组 $\textit{nums}[j+1,..i]$ 删除，使得剩余元素之和模 $p$ 的值为 $0$ 。

因此，如果存在一个 $target = (cur - k + p) \bmod p$ ，那么我们可以更新答案为 $\min(ans, i - j)$ 。接下来，我们更新 $last[cur]$ 的值为 $i$ 。继续遍历数组 $\textit{nums}$ ，直到遍历结束，即可得到答案。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $\textit{nums}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        k = sum(nums) % p
        if k == 0:
            return 0
        last = {0: -1}
        cur = 0
        ans = len(nums)
        for i, x in enumerate(nums):
            cur = (cur + x) % p
            target = (cur - k + p) % p
            if target in last:
                ans = min(ans, i - last[target])
            last[cur] = i
        return -1 if ans == len(nums) else ans

speed

复杂度分析

指标	值
时间	O(n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Do you know how to use prefix sums to avoid checking every subarray explicitly?
question_mark
Can you leverage modulo arithmetic with a hash map to identify candidate subarrays efficiently?
question_mark
Think about edge cases where the array sum is already divisible by p or where no subarray can satisfy the condition.

warning

常见陷阱

外企场景

error
Forgetting that removing the entire array is not allowed can lead to incorrect -1 handling.
error
Not using modulo operation on prefix sums can result in overflow or incorrect subarray matches.
error
Failing to update the minimum subarray length correctly when multiple candidates exist can return the wrong answer.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Instead of the smallest subarray, find the largest subarray that must be removed to achieve divisibility by p.
arrow_right_alt
Allow removal of multiple non-contiguous elements to make the sum divisible by p, requiring a different hashing strategy.
arrow_right_alt
Solve the problem when p is not fixed but given as a list of possible divisors to test for each.

help

常见问题

外企场景

继续练习

#1546 和为目标值且不重叠的非空子数组的最大数目 #1658 将 x 减到 0 的最小操作数 #1674 使数组互补的最少操作次数