這一題的難點在于模運算,對模運算足夠了解,對式子進行變換就很容易得到結果,本質上還是一道前綴和+哈希表的題
這里重點講一下模運算。
常見的模運算的用法
(a-b)%k==0等價于 a%k=b%k
而在這一題中由于多了一個len,(數組的總和)即 len-(sum[j]-sum[i])%p=0
len%p=(sum[j]-sum[i])%p
因為兩邊都是%p
所以可以把%p提出來,對等式進行移項
(sum[j]-len)%p=sum[i]%p
而減法的模運算:
(a?b)%p=((a%p)?(b%p)+p)%p
也就是 ((sum[j]%p)-(len%p)+p)%p=sum[i]%p
加法的模運算和乘法的模運算都是同理
進行多次%p的原因是為了避免負數,就這一題我們可以知道的是sum[j]-len一定是小于0的
當弄清楚模運算后代碼就好寫了
class Solution {
public:long long sum[100005];
unordered_map<int,int> mp;int minSubarray(vector<int>& nums, int p) {for(int i=0;i<nums.size();i++){sum[i+1]=sum[i]+nums[i];}long long len=sum[nums.size()];//(len-(sum[j]-sum[i]))%k==0;// len%k==(sum[j]-sum[i])%k//s[right]- s[left]≡x(modp)//((s[right]-x)modp+p)modp=s[left]modp//(a+b)%k==0//a%k==b%kif(len%p==0){return 0;}mp[0]=0;int ans=INT_MAX;for(int j=0;j<nums.size();j++){if(mp.count((sum[j+1]%p-len%p+p)%p)){int i=mp[(sum[j+1]%p-len%p+p)%p]; ans=min(ans,j+1-i);} mp[sum[j+1]%p]=j+1;} if(ans==INT_MAX||ans==nums.size()){return -1;}else{return ans;}}
};
要注意的是如果本身數組和%p就已經滿足條件,那么就不用除去子數組,提前返回0
,如果移除的數組和是原數組和本身或者不存在符合條件的情況,那么都return -1
最后
時間復雜度O(n);