使数组和能被 P 整除

标签: 数组 哈希表 前缀和

难度: Medium

给你一个正整数数组 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 <= 105
  • 1 <= nums[i] <= 109
  • 1 <= p <= 109

Submission

运行时间: 91 ms

内存: 35.5 MB

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

        cur = 0 
        pos={0:-1} # {当前前缀和余数:pos} # 不能初始化成{0:0}，这样会和{nums[0]%p:0}冲突
        res = float('inf')

        for i in range(n):
            cur +=nums[i]
            y = cur%p 
            x = (cur%p-k+p) % p
            
            if x in pos:
                res = min(res, i-pos[x])

            pos[y]=i
        return res if res<n else -1

Explain

题解采用了前缀和与哈希表来解决问题。首先，计算数组总和的余数 k（与 p 的余数），如果 k 为 0，则整个数组和已经是 p 的倍数，直接返回 0。如果 k 不为 0，需要找到一个最短的子数组，移除后剩余部分的和为 p 的倍数。通过逐步构建前缀和，并计算每一步的余数 y 存储到哈希表中（键为余数，值为对应的索引）。为了找到符合条件的子数组，计算每个位置的前缀和余数 x，它是将当前余数调整到我们需要的余数。如果这个 x 出现在哈希表中，则说明从该位置到当前位置的子数组是一个候选子数组。通过比较和更新最小长度，最终得到结果。

时间复杂度: O(n)

空间复杂度: O(n)

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

        cur = 0
        pos = {0: -1} # 存储余数到索引的映射，初始余数0的位置设为-1
        res = float('inf') # 初始化最短长度为无穷大

        for i in range(n):
            cur += nums[i] # 更新当前前缀和
            y = cur % p # 计算当前前缀和的余数
            x = (y - k + p) % p # 计算需要找的余数

            if x in pos:
                res = min(res, i - pos[x]) # 如果找到需要的余数，则尝试更新最短子数组长度

            pos[y] = i # 更新余数对应的最新索引
        return res if res < n else -1 # 如果找到有效子数组，返回长度，否则返回-1

Explore

在求解该问题时，我们的目标是通过移除数组中的某个子数组来使得剩余部分的和能被 p 整除。计算出前缀和的余数 y 后，我们需要进一步找到一个子数组，使得移除它之后的数组和的余数为 0。通过计算新的余数 x = (y - k + p) % p，我们实际上是在查找一个之前的前缀和的余数，使得两者的差恰好等于数组总和的余数 k，这样移除两者之间的部分后，余数就从 y 变为 0，达到了题目的要求。这是因为如果两个前缀和的余数之差等于 k，那么这两个前缀和之间的部分（即子数组）的和必定是 p 的倍数。

在哈希表中设置初始余数 0 的位置为 -1 是为了处理从数组开始到当前位置的子数组可以直接使得和为 p 的倍数的情况。例如，如果数组的前几个元素之和就已经是 p 的倍数，那么这时候的前缀和的余数为 0。如果不设置余数 0 的初始位置为 -1，我们就无法正确地计算出从数组开始到当前位置的子数组长度，因为通常哈希表记录的是前缀和余数第一次出现的位置。设置为 -1 可以让我们通过计算 i - (-1) = i + 1 来得到正确的子数组长度。

哈希表在这个算法中用来存储某个余数第一次出现的索引位置。当我们在遍历数组并计算当前元素的前缀和的余数 y 时，我们计算出调整后的余数 x。如果这个 x 已经在哈希表中存在，这意味着从哈希表中 x 对应的索引位置+1到当前索引 i 的子数组的和是 p 的倍数。这是因为这两个位置的前缀和的余数相同或者符合我们调整后的余数关系，从而使得这部分子数组和的余数为 0。通过记录并更新这些子数组的长度，我们可以找到最短的符合条件的子数组。每次找到符合条件的子数组时，我们比较并更新记录的最短长度，直到遍历完整个数组。