这一题的难点在于模运算,对模运算足够了解,对式子进行变换就很容易得到结果,本质上还是一道前缀和+哈希表的题
这里重点讲一下模运算。
常见的模运算的用法
(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);