力扣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;}};