ARST打卡第343周

 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

class Solution {
public:
    int minSubarray(vector<int>& nums, int p) {
        // 题目意思: 找最短的连续子数组，移除之后使得剩下的和能被p整除
        // 等价于：找最短的连续子数组，其和 mod p == (总和 mod p)
        unordered_map<int, int> mp;  // 记录前缀和mod p 到下标的映射
        long long sum = 0;
        for (int x : nums) sum += x;
        int need = sum % p;  // 最后要去掉的子数组的sum%p==need
        if (need == 0) return 0;

        mp[0] = -1;  // 让前缀和0成立
        int n = nums.size();
        int res = n;
        long long cur = 0;
        for (int i = 0; i < n; ++i) {
            cur = (cur + nums[i]) % p;
            // 看能不能找到前面的前缀和使得 (cur - prev + p) % p == need
            // 即 prev = (cur - need + p) % p
            int prev = (cur - need + p) % p;
            if (mp.count(prev)) {
                res = min(res, i - mp[prev]);
            }
            mp[cur] = i;
        }
        return res == n ? -1 : res;
    }
};