我是靠谱客的博主 过时花卷，最近开发中收集的这篇文章主要介绍【算法/前缀和/哈希表优化】题解+详细备注(共9题)560.和为K的子数组1248.统计「优美子数组」525.连续数组1124.表现良好的最长时间段面试题17.05.字母与数字974.和可被K整除的子数组523.连续的子数组和1524.和为奇数的子数组数目1590.使数组和能被P整除，觉得挺不错的，现在分享给大家，希望可以做个参考。
概述
【算法/前缀和/哈希表优化】
- 560.和为K的子数组
- 1248.统计「优美子数组」
- 525.连续数组
- 1124.表现良好的最长时间段
- 面试题17.05.字母与数字
- 974.和可被K整除的子数组
- 523.连续的子数组和
- 1524.和为奇数的子数组数目
- 1590.使数组和能被P整除
560.和为K的子数组
class Solution {
public:
// [j..i]的子数组和：pre[i+1] - pre[j]
// pre[i+1]-pre[j] == k
// 关键点是想到：考虑以 i 结尾的和为 k 的连续子数组个数时只要统计有多少个前缀和为pre[i+1]−k 的 pre[j] 即可
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> mp;
mp[0] = 1;
int count = 0;
int n = nums.size();
vector<int> pre(n+1);
for(int i{};i<n;++i){
pre[i+1] = pre[i] + nums[i];
if (mp.find(pre[i+1]- k) != mp.end()) {
count += mp[pre[i+1]- k];
}
mp[pre[i+1]]++;
}
return count;
}
};
1248.统计「优美子数组」
class Solution {
public:
// 关键是pre前缀的定义：定义pre[i+1] 为 [0..i] 中奇数的个数，所以pre[i+1] = pre[i] + (nums[i]&1)
// [j..i] 这个子数组里的奇数个数恰好为 k 这个条件我们可以转化为 pre[i+1]−pre[j]==k
// pre[j] = pre[i+1] - k
int numberOfSubarrays(vector<int>& nums, int k) {
unordered_map<int, int> mp;
mp[0] = 1;
int count = 0;
int n = nums.size();
vector<int> pre(n+1);
for(int i{};i<n;++i){
pre[i+1] = pre[i] + (nums[i]&1);
if (mp.find(pre[i+1]- k) != mp.end()) {
count += mp[pre[i+1]- k];
}
mp[pre[i+1]]++;
}
return count;
}
};
525.连续数组
class Solution {
public:
// 将原问题转化为求：求最长的连续子数组，其元素和为 0；所以pre[i+1] - pre[i] = 0
// [j..i] 这个子数组的和恰好为0 pre[i+1] - pre[j]==0
// pre[j] = pre[i+1] ，所以也就是找前缀和为pre[i+1]的下标
int findMaxLength(vector<int>& nums) {
unordered_map<int, int> mp;
mp[0] = -1;
int result= 0;
int n = nums.size();
vector<int> pre(n+1);
for(int i{};i<n;++i){
pre[i+1] = pre[i] + (nums[i] == 0 ? -1 : nums[i]);
if (mp.find(pre[i+1]) != mp.end()) {
int j = mp[pre[i+1]];
result = max(result,i-j);
}else mp[pre[i+1]] = i;
}
return result;
}
};
1124.表现良好的最长时间段
class Solution {
public:
// 前缀和大于0，[0，i]符合条件
// 前缀和小于0,在hash中找小于pre[i]的下标；且pre[i]-1的下标一定是小于pre[i]-2的下标
int longestWPI(vector<int>& hours) {
unordered_map<int, int> mp;
int result= 0;
int n = hours.size();
vector<int> pre(n+1);
for(int i{};i<n;++i){
pre[i+1] = pre[i] + (hours[i] > 8 ? 1 : -1);
// 只需记录一次即可，即记录最小的下标
if(!mp.count(pre[i+1]))
mp[pre[i+1]] = i;
if(pre[i+1] > 0){
result = i+1;
continue;
}
if(mp.count(pre[i+1]-1)){
result = max(result,i-mp[pre[i+1]-1]);
}
}
return result;
}
};
面试题17.05.字母与数字
class Solution {
public:
// 同525. 连续数组，只是需要在最长的集合中找左下标最小的集合
vector<string> findLongestSubarray(vector<string>& array) {
unordered_map<int, int> mp;
mp[0] = -1;
int result= 0;
int n = array.size();
vector<int> pre(n+1);
vector<pair<int,int>> vp;
for(int i{};i<n;++i){
pre[i+1] = pre[i] + (isdigit(array[i][0])? -1 : 1);
if (mp.find(pre[i+1]) != mp.end()) {
int j = mp[pre[i+1]];
if(i-j > result){
result = i-j;
vp.clear();
vp.push_back({j,i});
}else if(i-j == result){
vp.push_back({j,i});
}
}else mp[pre[i+1]] = i;
}
if(vp.size() == 0) return {};
sort(vp.begin(),vp.end());
return vector<string>(array.begin()+vp[0].first + 1,array.begin()+vp[0].second+1);
}
};
974.和可被K整除的子数组
class Solution {
public:
// 关键是想到：(preSum[i+1]−preSum[j]) mod K== 0
// 即：preSum[j] mod K == preSum[i+1] mod K
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> mp;// 记录前缀和mod k的数量
// 注意的一个边界条件是，我们需要对哈希表初始化，记录 record[0]=1，这样就考虑了前缀和本身被 k 整除的情况
mp[0] = 1;
int n = nums.size();
int result{};
vector<int> pre(n+1);
for(int i{};i<n;++i){
pre[i+1] = pre[i] + nums[i];
// 注意 C++ 取模的特殊性，当被除数为负数时取模结果为负数，需要纠正
// 这个操作不是在简单的取绝对值，负数的取模运算公式如下
int preMod = (pre[i+1]%k + k)%k;
if (mp.find(preMod) != mp.end()) {
result += mp[preMod];
}
mp[preMod]++;
}
return result ;
}
};
523.连续的子数组和
class Solution {
public:
// 关键是想到：(preSum[i+1]−preSum[j]) mod K== 0
// 即：preSum[j] mod K == preSum[i+1] mod K
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> mp;// 记录前缀和mod k的数量
// 注意的一个边界条件是，我们需要对哈希表初始化，记录 record[0]=1，这样就考虑了前缀和本身被 k 整除的情况
mp[0] = -1;
int n = nums.size();
int result{};
vector<int> pre(n+1);
for(int i{};i<n;++i){
pre[i+1] = pre[i] + nums[i];
// 注意 C++ 取模的特殊性，当被除数为负数时取模结果为负数，需要纠正
// 这个操作不是在简单的取绝对值，负数的取模运算公式如下（需要关注int溢出）
int preMod = ((long long)pre[i+1]%k + k)%k;
if (mp.find(preMod) != mp.end()) {
int left = mp[preMod];
if(i-left >= 2) return true;
}else{
// 一定要放在else里面，保证左下标是最小的
mp[preMod] = i;
}
}
return false;
}
};
1524.和为奇数的子数组数目
class Solution {
public:
// 确定：奇数+偶数 = 奇数
// 然后利用前缀和进行奇偶判断
int numOfSubarrays(vector<int>& arr) {
const int MODULO = 1000000007;
int odd{};
int even{1};
int result{};
int n = arr.size();
vector<int> pre(n+1);
for(int i{};i < n;++i){
pre[i+1] = pre[i] + arr[i];
int preMod = pre[i+1]%2;
result = (result + (preMod == 0 ?odd : even))%MODULO;
if(preMod == 0) even++;
else odd++;
}
return result;
}
};
1590.使数组和能被P整除
class Solution {
public:
// 设删除的子数组的和：del = preSum[i+1] - preSum[j]
// 设总和为sums
// 根据题意得：(sums- del ) % p == 0
// 再由同余定理可知: (sums- del ) % p == 0
// sums % p = (preSum[i+1]- preSum[j]) % p
// (sums + preSum[j]) % p = preSum[i+1] % p
int minSubarray(vector<int>& nums, int p) {
unordered_map<int, int> mp;
// 注意的一个边界条件是，我们需要对哈希表初始化，记录 mp[0]=-1。
// 因为有一个特殊情形, 当区间和(del )对应的前缀和之差中被减数(即这里的preSum[i])%p得到的余数是0时, 区间的起点index会成为0。此时的被减数变得可有可无了, 长度按更长的算, 即j+1或j-(-1)。
mp[0] = -1;
int n = nums.size();
int result{n};
// 初始值要设为0.0，不然依然会溢出
long long sums = accumulate(nums.begin(),nums.end(),0.0);
if(sums < p) return -1;
int mod = sums % p;
if(0 == mod) return 0;
vector<long long> pre(n+1);
for(int i{};i<n;++i){
pre[i+1] = pre[i] + nums[i];
int curMod = pre[i+1] % p;
// 注意 C++ 取模的特殊性，当被除数为负数时取模结果为负数，需要纠正
// 这个操作不是在简单的取绝对值，负数的取模运算公式如下
int target = (curMod - mod + p) % p;
if (mp.find(target) != mp.end()) {
int j = mp[target];
result = min(i-j,result);
}
mp[curMod] = i;
}
return result == n ? -1 : result;
}
};
最后
以上就是过时花卷为你收集整理的【算法/前缀和/哈希表优化】题解+详细备注(共9题)560.和为K的子数组1248.统计「优美子数组」525.连续数组1124.表现良好的最长时间段面试题17.05.字母与数字974.和可被K整除的子数组523.连续的子数组和1524.和为奇数的子数组数目1590.使数组和能被P整除的全部内容，希望文章能够帮你解决【算法/前缀和/哈希表优化】题解+详细备注(共9题)560.和为K的子数组1248.统计「优美子数组」525.连续数组1124.表现良好的最长时间段面试题17.05.字母与数字974.和可被K整除的子数组523.连续的子数组和1524.和为奇数的子数组数目1590.使数组和能被P整除所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复