使数组和能被 P 整除

Leetcode题目链接

描述

详见中文题目链接。

解答

class Solution {
public:
    int minSubarray(vector<int>& nums, int p) {
        int mod = accumulate(nums.begin(), nums.end(), 0LL) % p;
        if (!mod) return 0;

        int n = nums.size();
        int res = n;

        unordered_map<int, int> prefixMap;
        prefixMap[0] = -1;

        int current = 0;
        for (int i = 0; i < n; i++) {
            current = (current + nums[i]) % p;
            // int find = current >= mod ? (current - mod) : (current + p - mod);
            int toFind = (current + p - mod) % p;
            if (prefixMap.find(toFind) != prefixMap.end()) {
                res = min(res, i - prefixMap[toFind]);
            }
            prefixMap[current] = i;
        }

        return res == n ? -1 : res;
    }
};