【Leetcode Daily】974和可被K整除的子数组

发表于2025-07-10|更新于2025-07-10|力扣日常 | LeetcodeDaily

|总字数:279|阅读时长:1分钟|浏览量:

题目浅析

想查看原题可以点击题目链接。
简单地说，就是给一个整数数组和一个整数 k，要求其中所有子数组和能被 k 整除的数量。

思路分享

前缀和的思路，可以参考【Leetcode Daily】303区域和检索-数组不可变
和之前的有些不同，发现有关取模的题目，大多都是判断取模后的内容来判断。前缀和是从下标零开始的一段子数组和，那么如果其中有一段子数组可以被 k 整除，可以写成 (i - j) % k == 0，换句话就是 i % k == j % k，题目也就转换成了找前缀和中，有多少组取模后的值相同的经典枚举情况。

https://leetcode.cn/problems/subarray-sums-divisible-by-k/solutions/22267/he-ke-bei-kzheng-chu-de-zi-shu-zu-by-lenn123/

代码解答（强烈建议自行解答后再看）

参考题解

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        s = list(accumulate(nums, initial=0))
        rec = defaultdict(int)
        ans = 0
        for i in s:
            index = i % k
            ans += rec[index]
            rec[index] += 1
        return ans

文章作者: 陆爻齐-LuYaoQi

文章链接: http://hslix.github.io/posts/3348efaa.html

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 LuYaoQi's Blogs！

Algorithm 枚举前缀和

相关推荐

【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: ...

【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 =...

【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++) { ...

【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 =...

【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: ...

【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) { ...

数据加载中