🔗 🟡 1590. Make Sum Divisible by P 2039

tags: `Biweekly Contest 35` `陣列(Array)` `前綴和(Prefix Sum)` `雜湊表(Hash Table)`

題意

給定一個正整數陣列 $nums$ 和一個正整數 $p$ 。

你現在需要移除陣列中的一個子陣列，使得剩餘元素的總和能被 $p$ 整除，但 不允許 移除整個陣列。

返回你需要移除的最小子陣列的長度，如果無法實現則返回 $-1$ 。

其中 子陣列(Subarray) 的定義為陣列中連續的一段元素。

約束條件

$1 \leq \text{nums.length} \leq 10^5$
$1 \leq \text{nums[i]} \leq 10^9$
$1 \leq p \leq 10^9$

思路：前綴和(Prefix Sum) + 雜湊表(Hash Table)

假設以下的取餘運算皆為正餘數，即 $x \bmod p$ 的值在 $[0, p-1]$ 之間。

首先思考要移除的子陣列有甚麼性質。令 $s$ 為陣列 $nums$ 的總和、 $s_{remove}$ 為要移除的子陣列的總和，則根據題意， $s - s_{remove} \bmod p = 0$ 。根據同餘的性質，由於移除後剩餘元素的總和能被 $p$ 整除，因此 $s$ 和 $s_{remove}$ 對 $p$ 取模後的餘數相同，令其為 $r$ ，即 $s \bmod p = s_{remove} \bmod p = r$ 。

而要求一段連續的子陣列的總和，可以使用前綴和(Prefix Sum)來求解。令 $s[i] = \displaystyle\sum_{j=0}^{i} nums[j]$ ，則 $s[r] - s[l-1]$ 就是陣列 $nums$ 的第 $l$ 項到第 $r$ 項的總和。由於我們只關心 $s \bmod p$ 的餘數，因此我們只需要維護前綴和對 $p$ 取模後的餘數即可，即 $s^{\prime}[i] = s[i] \bmod p$ 。

根據上述說明，對於每個 $i$ ，我們可以試圖找到一個 $j$ 使得 $\displaystyle(\sum_{k=j+1}^{i} nums[k]) \bmod p = r$ 。換句話說，對於 $s^{\prime}[i]$ ，我們需要關注是否存在一個 $s^{\prime}[j]$ 使得 $s^{\prime}[j] = (s^{\prime}[i] - r) \bmod p$ 。

因此，我們可以使用雜湊表(Hash Table) 來存儲每個前綴和餘數出現的索引位置。但由於我們要使移除的子陣列長度最小，因此在這些索引位置中，我們只需要關心最大的索引位置即可。若存在一個索引 $j$ 滿足條件，則 $i - j$ 就是我們要找的子陣列長度（因為這個子陣列的索引是從下標 $j+1$ 到下標 $i$ ）。

具體步驟如下：

前綴和計算：遍歷陣列，同時計算前綴和，並對 $p$ 取模。這樣我們可以快速得到任意子陣列的總和對 $p$ 的餘數。
雜湊表存儲：使用一個雜湊表來存儲每個前綴和的模值對應的最晚出現的索引。這樣在遍歷過程中，我們可以快速查找是否存在一個之前的前綴和，使得當前前綴和減去這個之前的前綴和的模值等於 $r$ ，從而確定需要移除的子陣列的位置和長度。
最小子陣列長度更新：在遍歷的過程中，不斷更新找到的最小子陣列長度，最終返回這個最小值。如果遍歷結束後仍未找到滿足條件的子陣列，則返回 $-1$ 。

此外，若 $r = 0$ ，則不需要移除任何子陣列，直接返回 $0$ 即可。而顯然移除所有元素也會滿足條件，但題目限制我們不能移除所有元素，因此若最後答案等於陣列長度，則返回 $-1$ 。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ $O (n)$ ，其中 $n$ $n$ 是陣列 $nums$ $n u m s$ 的長度。
- 我們需要分別計算前綴和和查找雜湊表。但這兩個過程其實可以合併，因此實際上只需要遍歷陣列一次。
空間複雜度： $\mathcal{O}(\min(n, p))$ $O (min (n, p))$ ，
- 我們需要使用一個雜湊表來存儲每個前綴和的模值對應的最晚出現的索引位置，但前綴和的模值最多只有 $\min(n, p)$ 種可能。
- 之所以不使用陣列紀錄是因為 $p \leq 10^9$ ，可能會導致記憶體不足。

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        n = len(nums)
        r = sum(nums) % p
        if r == 0:
            return 0
        s = 0 # prefix sum
        pos = {0: -1}
        ans = n
        for i, x in enumerate(nums):
            s = (s + x) % p
            if (s - r) % p in pos:
                ans = min(ans, i - pos[(s - r) % p])
            pos[s] = i
        return ans if ans < n else -1

class Solution {
public:
    int minSubarray(vector<int>& nums, int p) {
        int n = nums.size();
        int r = 0;
        for (int x : nums) r = (r + x) % p;
        if (r == 0) return 0;
        unordered_map<int, int> pos;
        pos[0] = -1;
        int ans = n;
        int s = 0; // prefix sum
        for (int i = 0; i < n; ++i) {
            s = (s + nums[i]) % p;
            if (pos.find((s - r + p) % p) != pos.end()) {
                ans = min(ans, i - pos[(s - r + p) % p]);
            }
            pos[s] = i;
        }
        return ans < n ? ans : -1;
    }
};