题目

给你一个正整数数组 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

解题思路

假设数组所有元素的总和为 total_sum。

我们要移除一个子数组，设其和为 sub_sum，使得剩余的元素和能被 p 整除。

数学公式表达为：

$$(total_sum - sub_sum) \pmod p = 0$$

这意味着：

$$sub_sum \pmod p = total_sum \pmod p$$

结论：

我们需要在数组中找到一个最短的子数组，使得这个子数组的和对 p 取模后，等于整个数组和对 p 取模的值。

令 target = total_sum % p。

• 如果 target == 0，说明原数组和已经能被 p 整除，直接返回 0。
• 如果 target > 0，我们的目标就是找到一个子数组，满足 sub_sum % p == target，且长度最小。

计算子数组和通常使用前缀和。

设 $P[i]$ 为数组前 $i$ 个元素的和（即 nums[0...i]）。

子数组 nums[j...i] 的和可以表示为 $P[i] - P[j-1]$。

我们需要找到下标 $i$ 和 $j$（$j \le i$），使得：

$$(P[i] - P[j-1]) \pmod p = target$$

移项变换一下：

$$P[j-1] \pmod p = (P[i] \pmod p - target + p) \pmod p$$

这意味着：

当我们遍历数组，计算当前的前缀和模 p（即 $P[i] \pmod p$）时，我们需要回头去查找是否之前出现过一个前缀和模 p 的值，等于 (current_mod - target + p) % p。

1. 计算总和模数：先遍历一遍数组，算出所有元素的和模 p 的值，记为 target。如果 target 为 0，直接返回 0。
2. 初始化哈希表：创建一个哈希表（或字典），用来记录某个前缀和模值最后一次出现的索引。
   • Key: 前缀和 % p
   • Value: 该前缀和对应的下标
   • 初始状态：{0: -1}。这是为了处理从数组开头开始的子数组（即 $P[j-1]$ 为 0 的情况）。
3. 遍历寻找最短子数组：
   • 维护一个 current_sum（当前前缀和）和 min_len（最小长度，初始化为数组长度）。
   • 遍历数组，更新 current_sum。
   • 计算 current_mod = current_sum % p。
   • 计算我们需要寻找的历史前缀和模值：needed_mod = (current_mod - target + p) % p。
   • 查找：如果 needed_mod 存在于哈希表中，说明从 map[needed_mod] + 1 到当前位置 i 的子数组符合条件。
   • 更新结果：计算该子数组长度 i - map[needed_mod]，并更新 min_len。
   • 更新哈希表：将当前的 current_mod 和下标 i 存入哈希表。注意：如果有重复的模值，我们要覆盖旧的下标，因为我们想要子数组越短越好，所以下标越大越好（越靠近当前位置）。
4. 返回结果：
   • 如果 min_len 仍然等于数组总长度，说明必须移除整个数组才能满足（题目不允许），返回 -1。
   • 否则返回 min_len。

具体代码

func minSubarray(nums []int, p int) int {

    prefix := make([]int, len(nums) + 1)
    sum := 0
    // 前缀和数组
    for i := 1; i < len(prefix); i++ {
        prefix[i] = (prefix[i - 1] + nums[i - 1]) % p
        sum =  (sum + nums[i - 1]) % p
    }
    remain := sum % p
    if remain == 0 {
        return 0
    }
    // 哈希表
    hash := make(map[int]int)
    hash[0] = 0
    min_len := len(nums)
    for i := 1; i <= len(nums); i++ {
        needed_mod := (prefix[i] - remain + p) % p
        if _, ok := hash[needed_mod]; ok {
            min_len = min(min_len, i - hash[needed_mod])
        }
        hash[prefix[i]] = i
    }

    if min_len == len(nums) {
        return -1
    } else {
        return min_len
    }
}