【刷题7】寻找数组的中心下标、和为k的子数组、和可被k整除的子数组
一、寻找数组的中心下标
题目：
思路：前缀和思想
- 预处理一个前缀和数组和一个后缀和数组，当前指向的元素的值不包括在数组的元素和中；
- 前缀和数组的公式与后缀和数组的公式（注意：要根据题目要求变化，不能死记公式）
- 细节处理：f[0]和g[n-1]为了防止越界，提前初始化为0；处理前缀和数组正向遍历原数组，处理后缀和数组反向遍历原数组，都是从第二个元素开始遍历（反向同理）
代码：
class Solution {
public:
int pivotIndex(vector<int>& nums) {
int n = nums.size();
int f[n]; // 前缀和数组
int g[n]; // 后缀和数组
f[0] = 0, g[n-1] = 0; // 初始化
// 处理前缀和数组
for(int i=1; i<n; i++)
{
f[i] = f[i-1] + nums[i-1];
}
// 处理后缀和数组
for(int i=n-2; i>=0; i--)
{
g[i] = g[i+1] + nums[i+1];
}
// 找出中心下标
for(int i=0; i<n; i++)
{
if(f[i] == g[i]) return i;
}
return -1;
}
};
<除自身以外数组的乘积>根据本题变形
二、和为k的子数组
题目：
思路：前缀和+哈希表
- 哈希表，第一个int是前缀和，第二个int是该前缀和出现的次数
- sum在for循环遍历累加，充当前缀和，实际不需要一个新的数组
- ret就是返回的个数
- 前缀和与k之间有两种情况：大于和等于。等于的话sum-k=0，所以hash[0]=1
- 大于的话，sum = k + (sum-k)，也就是说，只要sum-k存在，那么就一定有和为k的子数组。所以遍历的过程中同时找hash[sum-k]的个数是否为0，不为0就加到ret去，加的是hash[sum-k]，hash[sum-k]就是个数
- 判断后再++当前的前缀和次数，即保存数据
- 为什么不能直接用k？因为是Sum做前缀和，不然谁跟k来作比较，而且就算可以比较，k与sum之间如果不相等可能会漏掉一些数据。只要sum-k出现过就有等于k的。特殊情况等于0的话就前面设置一下
- hash.count()使用：哈希表中存在该数据就返回1，否则返回0
代码：
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int n = nums.size();
unordered_map<int, int> hash;
hash[0] = 1;// 整个数组和为k
int sum = 0;// 变量充当前缀和
int ret = 0;
for(auto e:nums)
{
sum += e;
if(hash.count(sum-k)) ret += hash[sum-k];
hash[sum]++;
}
return ret;
}
};
三、和可被k整除的子数组
题目：
思路：前缀和+哈希表
- 大体思路与上一道题一样
- 同余定理，因为有负数
- 与上一题最大的区别：上一题，判断哈希表是否存在sum-k,将前缀和sum放入哈希表；本题，判断哈希表是否存在前缀和的余数，将余数放入哈希表
代码：
class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k) {
int n = nums.size();
unordered_map<int, int> hash;
hash[0] = 1;
int sum = 0, ret = 0;
for(auto e:nums)
{
sum += e;
int r = (sum%k+k)%k;//同余定理
if(hash.count(r)) ret += hash[r];
hash[r]++;
}
return ret;
}
};
原文地址：https://blog.csdn.net/2301_77459845/article/details/142793724
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！