C++ O(n) prefix sum
The method: Maintain a hash map of modded prefix sum and index. So we can get the shortest subarray satisfying the constraint at each last position.\n\nTime com
The method: Maintain a hash map of modded prefix sum and index. So we can get the shortest subarray satisfying the constraint at each last position.\n\nTime complexity: O(n)\nSpace complexity: O(n)\n\nHow to get the equation for x, the modded prefix sum of the start position which satisfies the constraint:\n(sum - (prefixSum - x) % p) % p == 0\n=> x = (preSum - sum) % p\n=> to deal with negative numbers: x = (p + preSum - sum) % p\n\n```\nclass Solution {\npublic:\n    int minSubarray(vector<int>& nums, int p) {\n        int n = nums.size();\n        int sum = 0;\n        for (int num : nums) {\n            sum = (sum + num) % p;\n        }\n        if (sum == 0) {\n            return 0;\n        }\n        unordered_map<int, int> preSums;\n        preSums[0] = -1;\n        int result = n;\n        for (int i = 0, preSum = 0; i < n; i++) {\n            preSum = (preSum + nums[i]) % p;\n            int x = (p + preSum - sum) % p;\n            if (preSums.find(x) != preSums.end()) {\n                result = min(result, i - preSums[x]);\n            }\n            preSums[preSum] = i;\n        }\n        if (result == n) {\n            return -1;\n        }\n        return result;\n    }\n};\n```
[]