力扣1590.使数组和能被P整除
力扣1590.使数组和能被P整除
-
同余
- 转化为求一段区间和余p为x
- i - j = x
- j = i - x
-
class Solution { public: int minSubarray(vector<int>& nums, int p) { int x = accumulate(nums.begin(),nums.end(),0LL) % p; if(x == 0) return 0; int n = nums.size(),ans = n,s = 0; unordered_map<int,int> last{{s,-1}}; for(int i=0;i<n;i++) { s = (s + nums[i]) % p; last[s] = i; auto it = last.find((s - x + p) % p); if(it != last.end()) ans = min(ans,i - it->second); } return ans < n ? ans : -1; } };