---

1590. 使数组和能被 P 整除

• 标签：数组、哈希表、前缀和
• 难度：中等

题目链接

• 1590. 使数组和能被 P 整除 - 力扣

题目大意

描述：给定一个正整数数组 $nums$ 和一个整数 $p$。可以删除数组中一个子数组（可以为空）。

要求：返回使得剩余元素的和能被 $p$ 整除所需删除的最小子数组长度。如果无法做到，返回 $-1$。

说明：

• $1 \le nums.length \le 10^5$。
• $1 \le nums[i] \le 10^9$。
• $1 \le p \le 10^9$。

示例：

• 示例 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：前缀和 + 哈希表

1. 核心思想

设整个数组的和为 $total$，删除子数组 $nums[l..r]$（下标从 $l$ 到 $r$）后，剩余和 = $total - sum(l..r)$。要求 $(total - sum(l..r)) \% p = 0$，即 $sum(l..r) \% p = total \% p$。

设 $target = total \% p$。如果 $target == 0$，不需要删除，返回 $0$。

否则，需要在数组中寻找和为 $target$（模 $p$ 意义下）的最短子数组。

设前缀和数组 $prefix[i] = (\sum_{k=0}^{i-1} nums[k]) \% p$，则子数组 $nums[l..r-1]$ 的和模 $p$ 为 $(prefix[r] - prefix[l] + p) \% p$。

条件 $(prefix[r] - prefix[l] + p) \% p = target$，即 $prefix[l] = (prefix[r] - target + p) \% p$。

所以我们遍历 $r$，用哈希表记录每个 $prefix$ 值最近出现的位置 $l$。对于当前 $r$，查找前缀和为 $(prefix[r] - target + p) \% p$ 的最右位置，子数组长度为 $r - l$。

2. 具体步骤

第 1 步：计算 $total = sum(nums)$，$target = total \% p$。如果 $target == 0$，返回 $0$。

第 2 步：初始化哈希表 $last\_pos$，记录每种前缀和模 $p$ 值的最后出现位置。初始 $last\_pos[0] = -1$。

第 3 步：遍历 $i = 0 \to n-1$，维护当前前缀和 $cur$：

• $cur = (cur + nums[i]) \% p$。
• 需要的前缀和 $need = (cur - target + p) \% p$。
• 如果 $need$ 在 $last\_pos$ 中，子数组长度 = $i - last\_pos[need]$，更新最小长度。
• 更新 $last\_pos[cur] = i$。

第 4 步：返回最小长度。如果没找到，返回 $-1$。

3. 正确性证明

• 剩余和能被 $p$ 整除 $\iff$ 删除的子数组和模 $p$ 等于整个数组和模 $p$。
• 对于每个右端点 $r$，我们希望在左边找到最近的 $l$ 使得 $prefix[l] = (prefix[r] - target) \% p$。
• 哈希表记录每种前缀和的最右位置，保证找到的子数组最短。

4. 举例说明

以 $nums = [3, 1, 4, 2], p = 6$ 为例：

$total = 10$，$target = 10 \% 6 = 4$。

• $i=0$，$cur = 3$，$need = (3-4+6)\%6 = 5$，$last\_pos[5]$ 不存在。$last\_pos[3]=0$。
• $i=1$，$cur = 4$，$need = (4-4+6)\%6 = 0$，$last\_pos[0]=-1$，长度 $1-(-1)=2$，$ans=2$。$last\_pos[4]=1$。
• $i=2$，$cur = 2$，$need = (2-4+6)\%6 = 4$，$last\_pos[4]=1$，长度 $2-1=1$，$ans=1$。$last\_pos[2]=2$。
• $i=3$，$cur = 4$，$need = 0$，$last\_pos[0]=-1$，长度 $3-(-1)=4$。

最短长度为 $1$，删除 $[2]$（即 $nums[2]=4$）。

验证：剩余 $[3,1,2]$，和 $6$，能被 $6$ 整除。

思路 1：代码

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        total = sum(nums)
        target = total % p
        if target == 0:
            return 0

        last_pos = {0: -1}
        cur = 0
        ans = len(nums)

        for i, x in enumerate(nums):
            cur = (cur + x) % p
            need = (cur - target + p) % p
            if need in last_pos:
                ans = min(ans, i - last_pos[need])
            last_pos[cur] = i

        return ans if ans < len(nums) else -1

思路 1：复杂度分析

• 时间复杂度：$O(n)$，一次遍历。
• 空间复杂度：$O(p)$，但实际存储的键最多 $n$ 个。$p$ 很大时，哈希表大小 $O(n)$。