原题链接:
https://leetcode.cn/problems/make-sum-divisible-by-p/

很有意思的一道前缀和的题目 直接从来没想过这种思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/*  
    记数组总和为S1 连续子数组为S2
    移除子数组模数为0 即 (S2 - S1) % MOD P = 0 
    根据模运算法则即 S2 % P = S1 % P
    用前缀和来表示子数组S2 = f[i] - f[j]
    即 S1 % P = (f[i] - f[j]) % P = f[i] % P - f[j] % P
    记 S1 % P = x 
    即为 f[j] % P   = f[i] % P - x
    使用hash表记录 f[j] % P (j 定义为i 前面的序列)
    因此不断右移的过程 即可同时保存 f[j] % P 同时计算f[i] % P - x 判断是否符合条件
*/
class Solution {
public:
    int minSubarray(vector<int>& nums, int p) {
        int n = nums.size();
        vector<int>s(n + 1,0);
        for(int i = 0 ; i < n; i++){
            s[i + 1] = (nums[i] + s[i]) % p;
        }
        int x = s[n];
        if(x  == 0){
            return 0;
        }

        unordered_map<int,int>hash;

        int ans = n + 1;

        for(int i = 0 ; i <= n ; i++){
            // 记录以i为结尾的 前缀和值的对应位置
            // 这里直接顺着来就可以了 因为要找的是前面的j
            hash[s[i]] = i;
            // 这里其实是处理 f[i] % P - x 会出现的负数的情况 保证值始终为正的
            auto it = hash.find((s[i] - x + p) % p);
            if(it != hash.end()){
                // 即存在前一个以j结尾的子序列其mod的值与 f[i] % P - x 相同的情况
                // 更新答案
                ans = min(ans,i - it->second);
            }
        }

        return ans < n ? ans : - 1;
    }
};