leetcode 1590. 使数组和能被 P 整除-Make Sum Divisible by P

Problem: 1590. 使数组和能被 P 整除-Make Sum Divisible by P耗时100%求出前缀和若总和sum p返回-1若sum % p0返回0否则考察长度从小到大0 - n-1的子数组累加和若满足条件直接返回最后返回-1是最下面的方案(sum - k) % Q 0则sum和k关于Q的余数是相同的所以对累加和求出余数resum%p只要看前面的累加和是否存在余数是(re - rem p) % p的结果就行target (re - rem p) % p拿到最短的距离的同余定理Codeclass Solution { public: int minSubarray(vectorint nums, int p) { int n nums.size(), rem, re, target, mi INT_MAX; long long sum 0; for(int i : nums) sum i; if(sum p) return -1; rem sum % p; if(rem 0) return 0; unordered_mapint, int ump; sum 0; ump[0] -1; for(int i 0; i n; i) { sum nums[i]; re sum % p; target (re - rem p) % p; if(ump.count(target) ! 0) { mi min(mi, i - ump[target]); } ump[re] i; } if(mi n) return -1; return mi; } };Codeclass Solution { public: int minSubarray(vectorint nums, int p) { vectorlong long prefix{0}; int n nums.size(), r; long long sum; for(int i : nums) prefix.push_back(prefix.back() i); sum prefix.back(); if(sum p) return -1; if(sum % p 0) return 0; for(int i 1; i n; i) { r n - i 1; for(int j 0; j r; j) { if((sum - (prefix[ji] - prefix[j])) % p 0) return i; } } return -1; } };