企业官网建设流程全解析

1. 除⾃⾝以外数组的乘积

除⾃⾝以外数组的乘积

解题思路：
由于题目限制了不能使用除法，因此不能采用全部相乘在除以nums[i]的方式解题。从暴力解法出发，我们只能将除nums[i]以外的元素相乘后逐个放入数组，但这样重复的操作太多，不符合O(N)的时间复杂度。因此，我们采用前缀和思想优化暴力解法。

1. 前缀和O(N)：对于返回数组中的每一个结果ret[i]，都是由两部分组成的：前面元素的乘积 *后面元素的乘积。因此，我们可以预处理出两个前缀和数组，一个数组存储每个数之前元素的乘积，另一个存之后元素的乘积。

classSolution{public:vector<int>productExceptSelf(vector<int>&nums){intn=nums.size();vector<int>fx(n,1);vector<int>gx(n,1);for(inti=1;i<n;i++){fx[i]=fx[i-1]*nums[i-1];}for(inti=n-2;i>=0;i--){gx[i]=gx[i+1]*nums[i+1];}vector<int>ret;for(inti=0;i<n;i++){intleft=fx[i];intright=gx[i];ret.push_back(left*right);}returnret;}};

2. 和为K的⼦数组

和为 k 的⼦数组

解题思路：

1. 暴力O(N^2)：固定起始位置向后枚举，每次加到末尾，统计数组中和为K的子数组个数。
2. 前缀和 + 哈希表时O(N)空O(N)：这道题和前缀和的例题类似，但如果只是单单预处理一个前缀和数组，后续还需要进行多次相减才能找到和为K的连续子数组个数，和暴力枚举貌似没区别。对此，我们引入哈希表存储，这样问题就转化为在数组中查找和为sum[i] - k的前缀和了。

classSolution{public:intsubarraySum(vector<int>&nums,intk){unordered_map<int,int>hash;intsum=0,cnt=0;hash[0]=1;for(autox:nums){sum+=x;if(hash.count(sum-k)==1){cnt+=hash[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。

解题思路：

1. 前缀和 + 哈希表时O(N)空O(N)：本题解题思路和上题类似，都是用哈希表+前缀和解决。根据同余定理，如果s1 % k和sum % k的余数相同，那么所求的子区间(sum - s1) % k == 0。这样问题就变为：找到在[0, i - 1]区间内，有多少前缀和的余数等于sum[i] % k的区间即可。

classSolution{public:intsubarraysDivByK(vector<int>&nums,intk){unordered_map<int,int>hash;//存储余数+出现次数intsum=0,ret=0;hash[0]=1;//0位置初始化为1，因为0是可以整除任何数的元素for(autox:nums){sum+=x;intr=(sum%k+k)%k;if(hash.count(r)){ret+=hash[r];//sum范围内所有余数为r的子区间都满足}hash[r]++;}returnret;}};

// 本期内容就到这里啦，如果对你有帮助，请三连支持！我是青云，我们下期见^_~