企业网站的主要类型,建个企业网站需要什么,wordpress 显示错误,哪个网站做美食好一点文章目录 Acwing#xff1a;前缀和示例2845.统计趣味子数组的数目思路容易理解的写法#xff1a;前缀和两层循环存在问题#xff1a;超时 优化写法#xff1a;两数之和思路#xff0c;转换为哈希表 前缀和#xff0c;就是求数组中某一段的所有元素的和。
求子数组中某一… 文章目录 Acwing前缀和示例2845.统计趣味子数组的数目思路容易理解的写法前缀和两层循环存在问题超时 优化写法两数之和思路转换为哈希表 前缀和就是求数组中某一段的所有元素的和。
求子数组中某一段数字的元素和只需要转换成两个数字的差值就可以了。
注意
只能求连续某一段区间的元素和一般来说前缀和需要在前面加一个0因为表示成两个数字的差的话如果前面不加0带有第一个数字的元素和无法表示成差值例如下图 Acwing前缀和示例 前缀和注意需要在最前面加上一个0所以前缀和数组大小是nums.size()1
#include iostream
#include cstring
#include algorithmusing namespace std;int main()
{int n, m, l, r;scanf(%d%d, n, m);int a[n], sum[n 1]; // s设置为n1是为了后面计算方便for (int i 0; i n; i ) scanf(%d, a[i]);sum[0] 0;for (int i 0; i n; i ) sum[i 1] sum[i] a[i];while (m -- ) {scanf(%d%d, l, r);printf(%d\n, sum[r] - sum[l - 1]); // 这里的l和r是1~n范围}return 0;
}
读入两个整数 n 和 m。n 是数组 a 的大小m 是查询的数量。定义数组 a 和 sum。a 用于存储输入的整数序列sum 用于存储前缀和。初始化 sum[0] 为0。使用循环计算 sum 数组其中 sum[i] 存储了数组 a 的前 i 个元素的和。循环进行 m 次查询每次查询读入两个整数 l 和 r然后输出区间 [l, r] 的和。这个和可以通过 sum[r] - sum[l - 1] 很快得到。注意这里的 l 和 r 是1-based也就是从1开始的而数组索引是0-based。所以可以直接用sum[r]-sum[l-1]因为r本身已经是对应的下标1了。
代码示例中的 sum[r] - sum[l - 1] 是核心点。为了理解它考虑下面的例子
a: 2 3 4 5
sum: 0 2 5 9 14为了得到 [2, 4] 这里的下标r和l是从1开始的子区间和 (即 3 4 5)我们可以使用 sum[4] - sum[2 - 1]结果为 12。
2845.统计趣味子数组的数目
给你一个下标从 0 开始的整数数组 nums 以及整数 modulo 和整数 k 。
请你找出并统计数组中 趣味子数组 的数目。
如果 子数组 nums[l..r] 满足下述条件则称其为 趣味子数组
在范围 [l, r] 内设 cnt 为满足 nums[i] % modulo k 的索引 i 的数量。并且 cnt % modulo k 。
以整数形式表示并返回趣味子数组的数目。
**注意**子数组是数组中的一个连续非空的元素序列。
示例 1
输入nums [3,2,4], modulo 2, k 1
输出3
解释在这个示例中趣味子数组分别是
子数组 nums[0..0] 也就是 [3] 。
- 在范围 [0, 0] 内只存在 1 个下标 i 0 满足 nums[i] % modulo k 。
- 因此 cnt 1 且 cnt % modulo k 。
子数组 nums[0..1] 也就是 [3,2] 。
- 在范围 [0, 1] 内只存在 1 个下标 i 0 满足 nums[i] % modulo k 。
- 因此 cnt 1 且 cnt % modulo k 。
子数组 nums[0..2] 也就是 [3,2,4] 。
- 在范围 [0, 2] 内只存在 1 个下标 i 0 满足 nums[i] % modulo k 。
- 因此 cnt 1 且 cnt % modulo k 。
可以证明不存在其他趣味子数组。因此答案为 3 。示例 2
输入nums [3,1,9,6], modulo 3, k 0
输出2
解释在这个示例中趣味子数组分别是
子数组 nums[0..3] 也就是 [3,1,9,6] 。
- 在范围 [0, 3] 内只存在 3 个下标 i 0, 2, 3 满足 nums[i] % modulo k 。
- 因此 cnt 3 且 cnt % modulo k 。
子数组 nums[1..1] 也就是 [1] 。
- 在范围 [1, 1] 内不存在下标满足 nums[i] % modulo k 。
- 因此 cnt 0 且 cnt % modulo k 。
可以证明不存在其他趣味子数组因此答案为 2 。提示
1 nums.length 10^5 1 nums[i] 10^91 modulo 10^90 k modulo
思路
首先思路就是运用前缀和单独开一个x数组遍历所有的nums[i]满足条件计数为1不满足条件计数为0。
这样的话子数组[l,r]内满足条件的数字个数直接就是子数组对应的x数组区间的和
容易理解的写法前缀和两层循环
#include vectorclass Solution {
public:long countInterestingSubarrays(std::vectorint nums, int modulo, int k) {int n nums.size();// 创建一个数组x来标记哪些数字模modulo后等于kstd::vectorint x(n, 0);// 创建一个前缀和数组std::vectorint sum(n 1, 0);// ----------- 前缀和计算开始 -----------for (int i 0; i n; i) {// 如果当前数字模modulo后等于k则在x数组中的对应位置标记为1if (nums[i] % modulo k) x[i] 1;// 计算前缀和当前位置的前缀和等于上一个位置的前缀和加上x数组中的当前值sum[i 1] sum[i] x[i];}// ----------- 前缀和计算结束 -----------// 初始化答案为0long ans 0;// 使用两重循环来检查所有可能的子数组和for (int l 0; l n; l) { // 子数组的开始位置for (int r l 1; r n; r) { // 子数组的结束位置// 如果子数组的和模modulo后等于k则增加答案的值if ((sum[r] - sum[l]) % modulo k) ans;}}// 返回答案return ans;}
};
存在问题超时
这种写法因为子数组两边都不定会超时时间复杂度是O(n^2)。 优化写法两数之和思路转换为哈希表
因为上面写法出现了超时我们可以用类似 两数之和 的套路来优化时间复杂度用map来减少一层循环。 两数之和的优化方法是遍历到nums[i]的时候先看看target-nums[i]是不是已经在map里面了。如果在直接返回不在就加到map里面继续遍历数字。遍历完了数组之后一定会收集所有的相加目标和的两数组合。 本题的优化方法是我们遍历sum[r]的时候找满足sum[r] - sum[l]) % modulo k条件的sum[l]是不是已经在哈希表里面了。哈希表map的作用是存放已经枚举过的sum。
#include vector
#include unordered_mapclass Solution {
public:long countInterestingSubarrays(std::vectorint nums, int modulo, int k) {int n nums.size();// x是原始数组sum是前缀和数组std::vectorint x(n, 0);std::vectorint sum(n 1, 0);// 使用unordered_map存储各个余数的位置数量std::unordered_mapint, int cnt;cnt[0] 1;long ans 0;for (int i 0; i n; i) {if (nums[i] % modulo k) x[i] 1;// 计算前缀和sum[i 1] (sum[i] x[i]) % modulo;int r sum[i 1];// 此处的索引就是在找满足条件的sum[l],r就是之前版本的sum[r]//需要满足的式子是(sum[r] - sum[l]) % modulo k//这里modulo的目的是为了防止r-k是负数m再取余结果还是0不会影响ans cnt[(r - k modulo) % modulo];// 更新哈希表中的计数这里是在更新sum[r]进哈希表(对应之前版本)cnt[r];}return ans;}
};
