分析Leetcode问题"974.可被K整除的子和“的时间复杂度 - 腾讯云开发者社区

题目给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。...示例：输入：A = [4,5,0,-2,-3,1], K = 5 输出：7 解释：有 7 个子数组满足其元素之和可被 K = 5 整除： [4, 5, 0, -2, -3, 1], [5], [5,...<= 10000 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/subarray-sums-divisible-by-k 著作权归领扣网络所有...) { // sum += A[i]+10000*K;//+10000*K，防止负数 sum += (A[i]%K+K)%K;//更专业的写法，效果同上...sum %= K;//除余sum在 0-K-1之间 count += m[sum];//前面 0 - K-1的状态有多少个，之间的连续和可被K整除 m[sum]++;

5931 0

LeetCode刷题DAY 25：和可被 K 整除的子数组

难度：中等关键词：同余定理、哈希表 ⭐️⭐️⭐️⭐️ 1 题目描述给定一个整数数组A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。...如输入 A = [4,5,0,-2,-3,1], K = 5，返回7（因为有7个连续子数组的和可被5整除）。...2 题解思路：哈希表本题跟LeetCode刷题DAY 17：和为k的子数组较为类似，定义pre(i)为[0,i]内的所有元素和，则有pre(i)=pre(i-1)+A[i]关系，要找有多少个(pre...(i)-pre(j-1))可被K整除。...在本题中，即有(pre(i)-pre(j-1))|K等同于pre(i)≡pre(j-1)(mod K)，因此我们在本题中可以建立哈希表，已余数为键，已该余数出现次数为值，计算哈希表中与pre(i)｜K取值一样的键对应值的和即可

4232 0

您找到你想要的搜索结果了吗？

是的

没有找到

LeetCode 1015. 可被 K 整除的最小整数（数学）

题目给定正整数 K，你需要找出可以被 K 整除的、仅包含数字 1 的最小正整数 N。返回 N 的长度。如果不存在这样的 N，就返回 -1。...示例 1：输入：1 输出：1 解释：最小的答案是 N = 1，其长度为 1。示例 2：输入：2 输出：-1 解释：不存在可被 2 整除的正整数 N 。...示例 3：输入：3 输出：3 解释：最小的答案是 N = 111，其长度为 3。...提示： 1 <= K <= 10^5 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/smallest-integer-divisible-by-k...解题 2和5的倍数显然不能被全是1的数整除，证明见官网题解提前取余，避免溢出 (n*10+1)%K = ((n%K)*10+1)%K class Solution { public: int

9112 0

Leetcode 1010. 总持续时间可被 60 整除的歌曲

题目描述在歌曲列表中，第 i 首歌曲的持续时间为 time[i] 秒。返回其总持续时间（以秒为单位）可被 60 整除的歌曲对的数量。...示例 1: 输入：[30,20,150,100,40] 输出：3 解释：这三对的总持续时间可被 60 整数： (time[0] = 30, time[2] = 150): 总持续时间 180 (...因为每个数字都是正数，不妨数组中每位数字对 60 取余数，这样要求的两个数字和为 60 或 0 即可，而不再是 60 的整数倍。...此时问题变为求和问题，可以以哈希表或者数组形式，存储每个元素值对应出现的次数。一次遍历即可获得最后的总对数。...对于元素值为 0 和 30 的情况，其对数的个数为 l*(l-1)/2，根据对称性，只需遍历 1～29 的情况即可。

5520 0

【刷题】前缀和进阶

适用于对数组有大量重复操作的问题，一维预处理较简单，二维比较复杂，画图分析可以顺利解决！ 2 Leetcode 560. 和为 K 的子数组上链接：560....count++; } } return count; } 定睛一看，这这这好像时间复杂度还不如暴力算法啊，这个的时间复杂度是O(n^2)...我们来分析一下假如我们枚举到第 i 个数字，得到了当前的前缀和 sum，那么如果想要得到满足和为 k 的子数组，就要寻找前缀和为 sum - k的数组那么前缀和为sum - k的数组怎么得到呢？...3 Leetcode 974. 和可被 K 整除的子数组上链接：974. 和可被 K 整除的子数组题目描述这个题目要求我们寻找和可以被 k 整除的子数组，很好理解。...整体框架与Leetcode 560. 和为 K 的子数组类似，但是如何计算出最长的子数组。

781 0

LeetCode 1010. 总持续时间可被 60 整除的歌曲（哈希）

题目在歌曲列表中，第 i 首歌曲的持续时间为 time[i] 秒。返回其总持续时间（以秒为单位）可被 60 整除的歌曲对的数量。...示例 1：输入：[30,20,150,100,40] 输出：3 解释：这三对的总持续时间可被 60 整数： (time[0] = 30, time[2] = 150): 总持续时间 180 (time...[1] = 20, time[3] = 100): 总持续时间 120 (time[1] = 20, time[4] = 40): 总持续时间 60 示例 2：输入：[60,60,60] 输出：3...解释：所有三对的总持续时间都是 120，可以被 60 整数。...提示： 1 <= time.length <= 60000 1 <= time[i] <= 500 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems

5611 0

LeetCode 523. 连续的子数组和（求余哈希）

题目给定一个包含非负数的数组和一个目标整数 k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，总和为 k 的倍数，即总和为 n*k，其中 n 也是一个整数。...示例 1: 输入: [23,2,4,6,7], k = 6 输出: True 解释: [2,4] 是一个大小为 2 的子数组，并且和为 6。...示例 2: 输入: [23,2,6,4,7], k = 6 输出: True 解释: [23,2,6,4,7]是大小为 5 的子数组，并且和为 42。...解题类似题目： LeetCode 560. 和为K的子数组（前缀和差分） LeetCode 862. 和至少为 K 的最短子数组（前缀和+deque单调栈） LeetCode 974....和可被 K 整除的子数组（哈希map）对前n个数求和，每次和对k取余，存入哈希表m[sum%k] = i 再次找到时，表明存在区间和为k的倍数 class Solution { public

4862 0

LeetCode 2261. 含最多 K 个可整除元素的子数组

题目给你一个整数数组 nums 和两个整数 k 和 p ，找出并返回满足要求的不同的子数组数，要求子数组中最多 k 个可被 p 整除的元素。...示例 1：输入：nums = [2,3,3,2,2], k = 2, p = 2 输出：11 解释：位于下标 0、3 和 4 的元素都可以被 p = 2 整除。...共计 11 个不同子数组都满足最多含 k = 2 个可以被 2 整除的元素： [2]、[2,3]、[2,3,3]、[2,3,3,2]、[3]、[3,3]、[3,3,2]、[3,3,2,2]、[3,2]、...注意，尽管子数组 [2] 和 [3] 在 nums 中出现不止一次，但统计时只计数一次。子数组 [2,3,3,2,2] 不满足条件，因为其中有 3 个元素可以被 2 整除。...此外，nums 中的每个子数组都满足最多 4 个元素可以被 1 整除。因为所有子数组互不相同，因此满足所有限制条件的子数组总数为 10 。

3013 0

LeetCode 560. 和为K的子数组（前缀和差分）

题目给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。...解题参考题目：LeetCode 1248. 统计「优美子数组」（要复习）的思路类似题目： LeetCode 862....和至少为 K 的最短子数组（前缀和+deque单调栈） LeetCode 525. 连续数组（前缀和+哈希） LeetCode 523....连续的子数组和（求余哈希） LeetCode 974....和可被 K 整除的子数组（哈希map） class Solution { public: int subarraySum(vector& nums, int k) {

7772 0

LeetCode 862. 和至少为 K 的最短子数组（前缀和+deque单调栈）

题目返回 A 的最短的非空连续子数组的长度，该子数组的和至少为 K 。如果没有和至少为 K 的非空子数组，返回 -1 。...示例 1：输入：A = [1], K = 1 输出：1 示例 2：输入：A = [1,2], K = 4 输出：-1 示例 3：输入：A = [2,-1,2], K = 3 输出：3 提示...： 1 <= A.length <= 50000 -10 ^ 5 <= A[i] <= 10 ^ 5 1 <= K <= 10 ^ 9 来源：力扣（LeetCode）链接：https://leetcode-cn.com...解题类似题目： LeetCode 560. 和为K的子数组（前缀和差分） LeetCode 523. 连续的子数组和（求余哈希） LeetCode 974....和可被 K 整除的子数组（哈希map）参考官方思路 deque存储前缀和的下标，队内前缀和需要严格单调递增跟队首的差值 >= k 时，记录最小长度，删除队首 ?

4342 0

LeetCode 周赛上分之旅 #44 同余前缀和问题与经典倍增 LCA 算法

统计趣味子数组的数目（Medium） https://leetcode.cn/problems/count-of-interesting-subarrays/ 题解（同余 + 前缀和 + 散列表）初步分析...：问题目标：统计数组中满足目标条件的子数组；目标条件：在子数组范围 [l, r] 内，设 cnt 为满足 nums[i] % m == k 的索引 i 的数量，并且 cnt %...大白话就是算一下有多少数的模是 k ，再判断个数的模是不是也是 k ；权重：对于满足 nums[i] % m == k 的元素，它对结果的贡献是 1 ，否则是 0 ；分析到这里，容易想到用前缀和实现...return ret } } 复杂度分析：时间复杂度： O(n) 线性遍历，单次查询时间为 O(1) ；空间复杂度： O(m) 散列表空间。...和为 K 的子数组 974. 和可被 K 整除的子数组 523. 连续的子数组和 525. 连续数组 ---- T4.

2763 0

LeetCode 930. 和相同的二元子数组（哈希+前缀和）

题目在由若干 0 和 1 组成的数组 A 中，有多少个和为 S 的非空子数组。...示例：输入：A = [1,0,1,0,1], S = 2 输出：4 解释：如下面黑体所示，有 4 个满足题目要求的子数组： [1,0,1,0,1] [1,0,1,0,1] [1,0,1,0,1] [...解题类似题目： LeetCode 523. 连续的子数组和（求余哈希） LeetCode 525. 连续数组（前缀和+哈希） LeetCode 560....和为K的子数组（前缀和差分） LeetCode 974. 和可被 K 整除的子数组（哈希map） LeetCode 1248....= m.end()) count += m[sum-S]; //前缀和减去S后的前缀和存在，中间段就是和为S的 m[sum]++; }

6291 0

【算法专题】前缀和

题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。请不要使用除法，且在 O(n) 时间复杂度内完成此题。...和为K的子数组题目链接 -> Leetcode -560.和为K的子数组 Leetcode -560.和为K的子数组题目：给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为...和可被K整除的子数组题目链接 -> Leetcode -974.和可被K整除的子数组 Leetcode -974.和可被K整除的子数组题目：给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被...k 整除的（连续、非空）子数组的数目。...连续数组题目链接 -> Leetcode -525.连续数组 Leetcode -525.连续数组题目：给定一个二进制数组 nums, 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度

901 0

TOP-K问题和向上调整算法和向下调整算法的时间复杂度问题的分析

TOP-K问题 TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等对于Top-K问题，能想到的最简单直接的方式就是排序...= 5; top_k(a, 1000, k); } 向上调整算法和向下调整算法的时间复杂度 因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，...多几个节点不影响最终结果)：我们令高度为h，节点个数n就等于2^(h)-1个那么在向上调整算法中：最坏情况下，最后一层的节点需要向上移动h-1次，依次类推，就得到总次数的表达式，然后再用错位相减法和...n和h的关系就能求出时间复杂度f（n）了在向下调整算法中：最坏情况下，倒数第二层节点向下只移动一次，第一层最多移动h-1次总结下来我们就会发现，向上调整算法中是多节点乘多层数的关系，而向下调整算法则是多节点乘少层数的关系...，我们进行比较就会发现其实向下调整算法的效率更高，所以在平常的排序和建堆中我们最常用的还是向下调整算法向上调整算法的时间复杂度为： n*log(n) 向下调整算法的时间复杂度为： log(n

851 0

【优选算法题练习】day8

一、974. 和可被 K 整除的子数组 1.题目简介 974....和可被 K 整除的子数组给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的（连续、非空）子数组的数目（子数组是数组的连续部分）。...连续数组给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。...) e = -1; } //将数组中的0转化为-1，这样问题就转变为和为0的最长连续子数组,推测为找和为sum的最短连续子数组 int sum = 0;...和为 K 的子数组 1.题目简介 560. 和为 K 的子数组给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。

1222 0

和为K的子数组（LeetCode 560）

文章目录 1.问题描述 2.难度等级 3.热门指数 4.解题思路方法一：枚举方法二：前缀和 + 哈希表优化参考文献 1.问题描述给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为...考虑以 i 结尾和为 k 的连续子数组个数，我们需要统计符合条件的下标 j 的个数，其中 0≤j≤i 且 [j…i] 这个子数组的和恰好为 k 。...可能有读者会认为假定我们确定了子数组的开头和结尾，还需要 O(n) 的时间复杂度遍历子数组来求和，那样复杂度就将达到 O(n^3) 从而无法通过所有测试用例。...时间复杂度： O(n^2)，其中 n 为数组的长度。枚举子数组开头和结尾需要 O(n^2) 的时间，其中求和需要 O(1) 的时间复杂度，因此总时间复杂度为 O(n^2)。空间复杂度： O(1)。...我们遍历数组的时间复杂度为 O(n)，中间利用哈希表查询删除的复杂度均为 O(1)，因此总时间复杂度为 O(n)。空间复杂度： O(n)，其中 n 为数组的长度。

1621 0

LeetCode题解——和为 k 的子数组

更新一篇发布在力扣上的题解，900+的watch记录一波，题目链接： https://leetcode-cn.com/problems/QTMn0o/ 解题思路 1、本题需要求出子数组之和为k的数组个数...我们可以先统计一下前n项的和值出现的次数，也就是所谓的前缀和，这里将前缀和为0也统计进来： 1）此时假设k=6，我们肉眼可见的数组和值为6的是【1，2，3】，那么对应到前缀和里面就是 3 这个位置，...它其实可以看成 3 - 0 得到的区间和值； 2）再假设k=7，那么我们可以发现数组和值为7的是【3，4】，此时我们可以发现在前缀和中没有找到和值为7的，那么说明该子数组的起始位置并非0；此时按照滑动窗口的思路就应该移动左指针...k的子数组了。...hash表中寻找的键值是sum-k，因为直接寻找k只可以找到那些起始位置为0的子数组，而寻找sum-k因为我们事先插入了一个0的键值，因此这里也不会忽略掉这种情况。

9162 0

LeetCode-560-和为K的子数组

# LeetCode-560-和为K的子数组给定一个整数数组和一个整数 **k，**你需要找到该数组中和为 k 的连续的子数组的个数。...https://leetcode-cn.com/problems/subarray-sum-equals-k/solution/dai-ni-da-tong-qian-zhui-he-cong-zui-ben-fang-fa-y...]−k 所以我们考虑以i结尾的和为k的连续子数组个数时只要统计有多少个前缀和为 sum[i]−k的 sum[j]即可。...我们建立哈希表 mp，以和为键，出现次数为对应的值，记录 sum[i]出现的次数，从左往右边更新 mp边计算答案，那么以 i结尾的答案 mp[sum[i]−k] 即可在 O(1)时间内得到。...最后的答案即为所有下标结尾的和为 k的子数组个数之和。需要注意的是，从左往右边更新边计算的时候已经保证了mp[sum[i]−k]里记录的 sum[j]的下标范围是 0≤j≤i 。

2221 0

Leetcode 560. 和为 K 的子数组

和为 K 的子数组题目描述：给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。...我们可以枚举[0..i]里所有的下标 j 来判断是否符合条件，可能有读者会认为假定我们确定了子数组的开头和结尾，还需要 O(n 的时间复杂度遍历子数组来求和，那样复杂度就将达到 O(n^3)，从而无法通过所有测试用例...枚举子数组开头和结尾需要 O(n^2)的时间，其中求和需要 O(1) 的时间复杂度，因此总时间复杂度为 O(n^2)。空间复杂度：O(1)。只需要常数空间存放若干变量。...pre[i]−pre[j−1]==k 简单移项可得符合条件的下标 jj 需要满足 pre[j−1]==pre[i]−k 所以我们考虑以 i结尾的和为 k 的连续子数组个数时只要统计有多少个前缀和为pre...return count; } }; 复杂度分析时间复杂度：O(n)，其中 n 为数组的长度。

6773 0

LeetCode560. 和为K的子数组

思路首先想到的是暴力求解，双重循环得出所有连续子串，但是多半要超时。没想到其他办法。看了题解，学到了前缀和的概念，这里的子串和等于end的前缀和减去start的前缀和。...在前缀和的基础上，结合了hash来优化，也就是两数之和那道题。两个地方需要注意。一、需要的前缀和可能出现多次，那么每次都得算上。二、前缀和为0也是一种情况，并且是必要的，需要手动添加。...题目给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。...数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。...// 子串长度为0（在母串最前面），前缀和为0，出现次数+1（原本为0） qzh.put(0, 1); // 前缀和 int sum

2212 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

LeetCode 974. 和可被 K 整除的子数组（哈希map）

LeetCode刷题DAY 25：和可被 K 整除的子数组

LeetCode 1015. 可被 K 整除的最小整数（数学）

Leetcode 1010. 总持续时间可被 60 整除的歌曲

【刷题】前缀和进阶

LeetCode 1010. 总持续时间可被 60 整除的歌曲（哈希）

LeetCode 523. 连续的子数组和（求余哈希）

LeetCode 2261. 含最多 K 个可整除元素的子数组

LeetCode 560. 和为K的子数组（前缀和差分）

LeetCode 862. 和至少为 K 的最短子数组（前缀和+deque单调栈）

LeetCode 周赛上分之旅 #44 同余前缀和问题与经典倍增 LCA 算法

LeetCode 930. 和相同的二元子数组（哈希+前缀和）

【算法专题】前缀和

TOP-K问题和向上调整算法和向下调整算法的时间复杂度问题的分析

【优选算法题练习】day8

和为K的子数组（LeetCode 560）

LeetCode题解——和为 k 的子数组

LeetCode-560-和为K的子数组

Leetcode 560. 和为 K 的子数组

LeetCode560. 和为K的子数组

扫码

相关资讯

热门标签

活动推荐

运营活动

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐