【Leetcode Daily】974和可被K整除的子数组
发表于|更新于|力扣日常 | LeetcodeDaily
|总字数:279|阅读时长:1分钟|浏览量:
题目浅析
想查看原题可以点击题目链接。
简单地说,就是给一个整数数组和一个整数 k,要求其中所有子数组和能被 k 整除的数量。
思路分享
前缀和的思路,可以参考 【Leetcode Daily】303区域和检索-数组不可变
和之前的有些不同,发现有关取模的题目,大多都是判断取模后的内容来判断。前缀和是从下标零开始的一段子数组和,那么如果其中有一段子数组可以被 k 整除,可以写成 (i - j) % k == 0,换句话就是 i % k == j % k,题目也就转换成了找前缀和中,有多少组取模后的值相同的经典枚举情况。
代码解答(强烈建议自行解答后再看)
- 参考题解
1 | class Solution: |
文章作者: 陆爻齐-LuYaoQi
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 LuYaoQi's Blogs!
相关推荐

2025-07-09
【Leetcode Daily】1524和为奇数的子数组数目
题目浅析 想查看原题可以点击题目链接。 简单地说,就是给一个整数数组,要求这个数组中所有子数组中和为奇数的数目。 思路分享 前缀和的思路,可以参考 【Leetcode Daily】303区域和检索-数组不可变 虽然是陆爻齐自己思考了出来,但如果没有提前知道是前缀和区域,应该是做不出来的。 回忆解题的过程,就是思考如何快速判定奇数区域时,对做了前缀和了数组观察偶然发现,只要记录此前的奇数和偶数的数目,就能方便地计算现有的数字与此前数字之前区域的和为奇数的数目。 代码解答(强烈建议自行解答后再看) 参考题解 123456789101112131415class Solution: def numOfSubarrays(self, arr: List[int]) -> int: s = list(accumulate(arr, initial=0)) even_num = 0 odd_num = 0 ans = 0 for i in s: if i%2 == 0: ...

2025-04-14
【Leetcode Daily】1534统计好三元组
题目浅析 想查看原题可以点击题目链接。 简单地说,就是给一个数组,要求统计其中所有满足要求三元组的数量。该要求是,两两之差,满足题目的三个数字。 思路分享 首先就是暴力解法,O(n^3),不过陆爻齐在普通的暴力上做了一点点剪枝,但终究还是暴力。 想要比较好的完成本题,就需要学习前缀和,总体的思路是固定三元组中的两个,通过要求来求得剩下一个值的范围,将该范围在前缀和中搜寻,符合则找到合适的三元组。 https://leetcode.cn/problems/count-good-triplets/?envType=daily-question&envId=2025-04-14 代码解答(强烈建议自行解答后再看) 陆爻齐小改良的暴力解法 12345678910111213141516171819class Solution {public: int countGoodTriplets(vector<int>& arr, int a, int b, int c) { int size =...

2025-04-11
【Leetcode Daily】2843统计对称整数的数目
题目浅析 想查看原题可以点击题目链接。 简单地说,就是给一个范围,统计这其中所有的对称整数的数目,对称整数要求有 2*n 位,n是整数,而且前n位数字之和与后n位数字之和相等。 思路分享 首先是普通的枚举法,毕竟本题是 easy,数字范围不大,暴力即可 ac。不过如何优雅简洁地暴力也是一门学问,如果是陆爻齐原来的想法,很可能会通过逐位模十来获取位数,但实际上处理数位用字符串更合适,结合上 reduce 函数可以间接地求得数位和,就有了下面的枚举写法。 接下来使用数位 dp 就可以解决当数字范围大时候的问题,但安排紧张,就先这样罢,要是能有时间把灵山的慢慢过就好力。 代码解答(强烈建议自行解答后再看) 枚举法 12345678910111213class Solution {public: int countSymmetricIntegers(int low, int high) { int result = 0; for (int i = low; i < high+1; i++) { ...

2025-05-29
【Leetcode Daily】930和相同的二元子数组
题目浅析 想查看原题可以点击题目链接。 简单地说,就是给一个整数数组和目标整数 goal,求子数组和恰好为 goal 的子数组数量。 思路分享 这是“恰好型滑动窗口”,本质上就是两个越长越合法的窗口结果之差。 实现有两个方式,一个是单独把滑动窗口划分一个函数,调用两次,求结果之差;另一个是只设置一次滑动窗口,不过要同时维护两个左指针,计算结果是直接累计数值之差。 代码解答(强烈建议自行解答后再看) 参考题解 123456789101112131415161718192021// 恰好型滑动窗口class Solution {public: int numSubarraysWithSum(vector<int>& nums, int goal) { int left1 = 0, left2 = 0, ans = 0; int sum1 = 0, sum2 = 0; int goal1 = goal, goal2 = goal+1; for (int right =...

2025-06-04
【Leetcode Daily】2389和有限的最长子序列
题目浅析 想查看原题可以点击题目链接。 简单地说,就是求一个数组的每个值,与另一个数组子序列和的关系,在子序列和不超过这个值的前提下,求最长子序列的长度。 思路分享 前缀和+二分 https://leetcode.cn/problems/longest-subsequence-with-limited-sum/solutions/1781111/fei-bao-li-zuo-fa-qian-zhui-he-er-fen-by-ny4m/ 为了使得子序列长度越长,要尽可能选取数值较小的元素。所以先排序,然后用前缀和得到各个子序列的和。 具体实现中,前缀和用 numeric 库的 partial_sum 实现,而二分就直接用 ranges 库的 upper_bound 函数,之所以不用 lower_bound 是因为本题要求“不超过”,而非小于。当然,用加一值的lower_cound也行。 代码解答(强烈建议自行解答后再看) 参考题解 123456789101112class Solution {public: ...

2025-06-08
【Leetcode Daily】1两数之和
题目浅析 想查看原题可以点击题目链接。 简单地说,就是给一个整型数组和目标值,从数组中找出两个值之和正好为目标值的下标,题目保证数组不重复,且必有唯一答案。要求两个下标不能相同。 思路分享 暴力法就是直接上两层循环,本题的目标是把时间复杂度降到O(n)。 下面就是灵神题解中介绍枚举方法,一个循环遍历一个值,每次遍历就在哈希表查找剩余另一个的值,没找到就把当前值和对应下标存哈希表。 https://leetcode.cn/problems/two-sum/solutions/2326193/dong-hua-cong-liang-shu-zhi-he-zhong-wo-0yvmj/ 注意,顺序很重要,不能先放哈希表再查找,不然就会找到相同下标的情况。 代码解答(强烈建议自行解答后再看) 参考题解 1234567891011121314class Solution {public: vector<int> twoSum(vector<int>& nums, int target) { ...
公告
不定时更新,记录所学所想
系列文章