1590. 使數組合能被P整除

思路

目標是要移除最少的子數組，讓剩下來的部分總和%k = 0， 此題跟3381. 長度可被 K 整除的子數組的最大元素和的想法類似，
都是使用前綴和 + 模運算的特性去加速計算速度。
當整個數組%k = 0時，滿足條件，不需要移除任何數字，返回 0。

題目要求去除掉一段子數組的數字總和滿足條件，寫成公式就長這樣

1. (sum - (prefix[j + 1] - prefix[i])) % p = 0
2. sum % p = (prefix[j + 1] - prefix[i]) % p
   （根據題目條件，前綴和數組是遞增的，因此不需要 + p 避免取模之後負數）
3. sum % p + prefix[i] % p = prefix[j + 1] % p;
4. prefix[i] % p = prefix[j + 1] % p - sum % p
5. prefix[i] % p = (prefix[i + 1] - sum + p) % p; 所以在遍歷時，記錄下prfiex[i] % p，並計算(prefix[i] - sum + p) % p，假如曾經出現在pos，
   那麼i - pos就是一個可能的解。

程式碼

class Solution {
public:
    int minSubarray(vector<int>& nums, int p) {
        int n = nums.size();
        long long sum = reduce(nums.begin(), nums.end(), 0LL); // 1e5 * 1e9 會溢出 int 
        sum %= p;
        if(!sum) return 0; // 不需要移除
        int res = n, prefix = 0; // 最糟的情況是全移除, res = n
        unordered_map<int, int> pos;
        pos[0] = -1;
        for(int i = 0; i < n; ++i) {
            prefix = (prefix + nums[i]) % p;
            int temp = (prefix - sum + p) % p;
            if(pos.find(temp) != pos.end()) {
                res = min(res, i - pos[temp]);
            }
            pos[prefix] = i;
        }
        return res == n ? -1 : res; // 如果無法移除, return -1
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(k)$