https://leetcode.com/problems/make-sum-divisible-by-p/ from Amazon

For something related to “devisible”, the first thing we should think of is remainder. Since it is asking about the shortest contiguous subarray, it’s very straightforward that we start thinking the prefix sum. So, to solve this, we can first compute the remainder of total array. If the remainder is 0, then it’s over. If we have remainder, then what we need to do is: for each position, we look back to find the nearest position which can compensate the remainder. For example, if the num is [3,1,4,2] and p=6, the prefix remainder is [3,4,2,4]. We need to find a subarray having 4 as the sum of remainder. So, if we are at position 1, as we can see, our prefix sum (num[0] and num[1]) is 4 already. So if we remove num[0] and num[1], our total sum will be 6 which is devisible of 6.

在Leetcode只要看到要找"可以被整除”，就要先想到用餘數。然後這裡又問到連續的subarray，很自然的會聯想到prefix sum，這題也不例外。我們先算prefix sum的餘數，整個array算完，如果最後餘數為0，那自然什麼都不用做。如果有餘數，我們就要找在之前的某個位置，用這兩個位置的prefix sum餘數相減後，會等於最後一個餘數(我們想扣掉的)。這樣就做完啦。唯一要注意的就是扣掉之後可能變負數，必須要加回p變回正數。

 1class Solution {
 2public:
 3    int minSubarray(vector<int>& nums, int p) {
 4        int N = nums.size();
 5        vector<int> pre(N);
 6        int cur = 0;
 7        for (int i=0; i<N; i++) {
 8            cur += nums[i];
 9            cur %= p;
10            pre[i] = cur;
11        }
12        if (pre.back()%p == 0) return 0;
13        int ans = INT_MAX;
14        int target = pre.back()%p;
15        unordered_map<int, int> mp;
16        mp[0] = -1;
17        for (int i=0; i<N; i++) {
18            int x = pre[i]-target;
19            if (x < 0) x += p;
20            if (mp.count(x) and (i!=N-1 or mp[x]!=-1)) {
21                ans = min(ans, i-mp[x]);
22            }
23            mp[pre[i]] = i;
24        }
25        return ans == INT_MAX ? -1 : ans;
26    }
27};