我是靠谱客的博主 过时花卷，这篇文章主要介绍【算法/前缀和/哈希表优化】题解+详细备注(共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的子数组
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class 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.统计「优美子数组」
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class 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.连续数组
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class 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.表现良好的最长时间段
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30class 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.字母与数字
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32class 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整除的子数组
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28class 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.连续的子数组和
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31class 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.和为奇数的子数组数目
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28class 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整除
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42class 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内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复