怎么做网站赚钱,徐州招聘网站哪个好,两学一做考试网站,大公司做网站标题#xff1a;【leetcode】前缀和#xff08;二#xff09;
水墨不写bug 正文开始#xff1a;
#xff08;一#xff09; 和为K的子数组 给你一个整数数组 nums 和一个整数 k #xff0c;请你统计并返回 该数组中和为 k 的子数组的个数 。 子数组是数组中元素的连续…标题【leetcode】前缀和二
水墨不写bug 正文开始
一 和为K的子数组 给你一个整数数组 nums 和一个整数 k 请你统计并返回 该数组中和为 k 的子数组的个数 。 子数组是数组中元素的连续非空序列。 示例 1 输入nums [1,1,1], k 2
输出2示例 2 输入nums [1,2,3], k 3
输出2提示 1 nums.length 2 * 10^4-1000 nums[i] 1000-10^7 k 10^7 思路一 暴力求解按照题目的描述来求解对于每一个数依次向后求和如果和k此时不能停下来ret继续遍历到整个数组。很显然此算法时间复杂度O(N^2)显然是会超时的算法。 思路二 我们可以换一种思路现在我们聚焦于以下标 i 为结尾的和为k的数组它们可能存在一个或者多个甚至根本不存在这时我们已经固定了一个下标i只需找到另一个下标即可假设 i 之前存在一个下标 i0[ i0 , i ](闭区间)的区间和为 k 这时算出 以 i 为结尾的前缀和 sum[i]这就将问题i之前是否存在i0使得[ i0 , i ](闭区间)的区间和为 k —转化为了— 下标 i 之前是否存在 i0 使得 i0 的前缀和为 sum[i] - k 这时如果你就按照以上思路来建立前缀和数组然后使用数组时你就会后悔自己做过的事情了在使用前缀和数组的时候对于一个指针cur i需要向前遍历数组在cur向后移动后还要进行向前遍历这个操作的时间复杂度为O(N^2),再加上建立前缀和数组的O(N),时间复杂度不减反增 这时我们就需要考虑一些操作是否能够同时进行将for的嵌套优化为一个for循环即可解决的问题。 如何理解呢其实一些互不影响的操作可以可以同时进行这时我们就可以在同一个循环中同时进行多个操作以此来减少for循环的个数以此来降低时间复杂度。 在本题中由于前缀和前n项和在每次循环中只使用一次所以可以创建一个变量通过对变量进行迭代累加求和来代替前缀和数组。 sum是不断变化的此时创建一个哈希表目的是用来记录此时sum的值在向后遍历时sum会递增。 创建变量ret累计和为k的字符串的个数 sum记录第i项的前缀和 创建hash表用来向前找sum-k时 ret 累加 答案sum-k的个数。 参考代码
class Solution {
public:int subarraySum(vectorint nums, int k) {unordered_mapint,int hash;int ret 0,sum 0;hash[0] 1;for(auto x:nums){sumx;if(hash.count(sum-k)) ret hash[sum-k];hash[sum];}return ret;}
};
二可被K整除的子数组 给定一个整数数组 nums 和一个整数 k 返回其中元素之和可被 k 整除的连续、非空 子数组 的数目。 子数组 是数组的 连续 部分。 示例 1 输入nums [4,5,0,-2,-3,1], k 5
输出7
解释
有 7 个子数组满足其元素之和可被 k 5 整除
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]示例 2: 输入: nums [5], k 9
输出: 0提示: 1 nums.length 3 * 104-104 nums[i] 1042 k 104 class Solution {
public:int subarraysDivByK(vectorint nums, int k) {unordered_mapint,int hash;hash[0%k] 1;int sum 0,ret 0;for(const auto e : nums){sum e;//计算前缀和//判断是否有符合要求的前缀和int aim (sum%kk)%k;if(hash.count(aim)) ret hash[aim];hash[aim];}return ret;}
}; 三连续数组 给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组并返回该子数组的长度。 示例 1: 输入: nums [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。 示例 2: 输入: nums [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。 提示 1 nums.length 105nums[i] 不是 0 就是 1 class Solution {
public:int findMaxLength(vectorint nums) {unordered_mapint,int hash;//存前缀和与对应的下标hash[0] -1;for( auto e:nums) if(e 0) e--;int ret 0,sum 0,n nums.size();for(int i 0;i n;i){sum nums[i];if(hash.count(sum)) ret max(ret,i-hash[sum]);else hash[sum] i;}return ret;}
}; 完~
未经作者同意禁止转载
