[LC优选算法#18] 前缀和 | 除⾃⾝以外数组的乘积 | 和为K的⼦数组 | 和可被K整除的⼦数组

1. 除⾃⾝以外数组的乘积除⾃⾝以外数组的乘积解题思路由于题目限制了不能使用除法因此不能采用全部相乘在除以nums[i]的方式解题。从暴力解法出发我们只能将除nums[i]以外的元素相乘后逐个放入数组但这样重复的操作太多不符合O(N)的时间复杂度。因此我们采用前缀和思想优化暴力解法。前缀和O(N)对于返回数组中的每一个结果ret[i]都是由两部分组成的前面元素的乘积 *后面元素的乘积。因此我们可以预处理出两个前缀和数组一个数组存储每个数之前元素的乘积另一个存之后元素的乘积。classSolution{public:vectorintproductExceptSelf(vectorintnums){intnnums.size();vectorintfx(n,1);vectorintgx(n,1);for(inti1;in;i){fx[i]fx[i-1]*nums[i-1];}for(intin-2;i0;i--){gx[i]gx[i1]*nums[i1];}vectorintret;for(inti0;in;i){intleftfx[i];intrightgx[i];ret.push_back(left*right);}returnret;}};2. 和为K的⼦数组和为 k 的⼦数组解题思路暴力O(N^2)固定起始位置向后枚举每次加到末尾统计数组中和为K的子数组个数。前缀和 哈希表时O(N)空O(N)这道题和前缀和的例题类似但如果只是单单预处理一个前缀和数组后续还需要进行多次相减才能找到和为K的连续子数组个数和暴力枚举貌似没区别。对此我们引入哈希表存储这样问题就转化为在数组中查找和为sum[i] - k的前缀和了。classSolution{public:intsubarraySum(vectorintnums,intk){unordered_mapint,inthash;intsum0,cnt0;hash[0]1;for(autox:nums){sumx;if(hash.count(sum-k)1){cnthash[sum-k];}hash[sum];}returncnt;}};3. 和可被K整除的⼦数组和可被K整除的⼦数组前置知识同余定理如果(a - b) % n 0那么我们可以得到一个结论a % n b % n反过来也成立。⽤⽂字叙述就是如果两个数相减的差能被 n 整除当且仅当这两个数对 n 取模的结果相同。负数取模修正C中对负数取模结果还会返回负数取模结果加上符号。我们需要对取模结果进行修正以(a % n n) % n的形式输出保证为正。例如-1 % 3 (-1 % 3 3) % 3 2。解题思路前缀和 哈希表时O(N)空O(N)本题解题思路和上题类似都是用哈希表前缀和解决。根据同余定理如果s1 % k和sum % k的余数相同那么所求的子区间(sum - s1) % k 0。这样问题就变为找到在[0, i - 1]区间内有多少前缀和的余数等于sum[i] % k的区间即可。classSolution{public:intsubarraysDivByK(vectorintnums,intk){unordered_mapint,inthash;//存储余数出现次数intsum0,ret0;hash[0]1;//0位置初始化为1因为0是可以整除任何数的元素for(autox:nums){sumx;intr(sum%kk)%k;if(hash.count(r)){rethash[r];//sum范围内所有余数为r的子区间都满足}hash[r];}returnret;}};// 本期内容就到这里啦如果对你有帮助请三连支持我是青云我们下期见^_~