【Leetcode Daily】1590使数组和能被P整除

发表于2025-11-30|更新于2025-11-30|力扣日常 | LeetcodeDaily

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

题目浅析

想查看原题可以点击题目链接。
简单地说，就是给一个数组和数字 p，现在可以移除数组内的最短长度的子数组，使得数组和能被 p 整除。

思路分享

本质上就是找到子数组和能与总数组和同余时，长度最小的情况。对于找子数组的前缀和区间两侧：(right - left)%p = num, (right-num)%p = left%p。
那么遍历前缀和，通过哈希表就能方便得记录前面子数组的余数情况，如果有匹配的左侧子数组，就记录当前长度。

https://leetcode.cn/problems/make-sum-divisible-by-p/solutions/2158435/tao-lu-qian-zhui-he-ha-xi-biao-pythonjav-rzl0/?envType=daily-question&envId=2025-11-30

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

参考题解

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        accu_sum = list(accumulate(nums, initial=0))
        left = accu_sum[-1] % p 
        if left == 0:
            return 0
            
        rec = {}
        ans = n = len(nums)
        for i, num in enumerate(accu_sum):
            rec[num % p] = i 
            last_index = rec.get((num-left) % p, -n)
            ans = min(ans, i-last_index)
        return ans if ans < n else -1

文章作者: 陆爻齐-LuYaoQi

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

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

Algorithm 前缀和哈希表

相关推荐

【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】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】303区域和检索-数组不可变

题目浅析想查看原题可以点击题目链接。简单地说，就是要求实现一个类，这个类能够返回数组中任意一个闭区间的数值和。思路分享这是前缀和的模板题，所谓前缀和的计算，正如其名，就是把数组从左往右一个个数值累加并记录。 https://leetcode.cn/problems/range-sum-query-immutable/solutions/2693498/qian-zhui-he-ji-qi-kuo-zhan-fu-ti-dan-py-vaar/ 实现方式很简单，但是有一点需要特别注意，就是留出第一位的 0.如果采用第一位就放第一位的数值，那么就需要特别处理闭区间左部为 0 的情况，但是如果第一位置零，第二位放第一个数值，第三位放前两个数值，这样子下去，取区间和就只要调整一下下标加一即可。代码解答（强烈建议自行解答后再看）参考题解 12345678910111213141516class NumArray: def __init__(self, nums: List[int]): s = [0] * (len(nums)+1) ...

【Leetcode Daily】3427变长子数组求和

题目浅析想查看原题可以点击题目链接。简单地说，就是给了一个整型数组，对其中的每一个元素，都要根据一个要求创建一个子数组，而题目要求则要返回这些所有子数组的数值和。思路分享前缀和的思路，可以参考【Leetcode Daily】303区域和检索-数组不可变由于题目子数组和求得的方式，可以通过前缀和方便完成，所以采用这种方法。重要的是，终于搞清楚了 Python 中 accumulate 函数到底是怎么形成的。对于 [1, 2, 3] 这样的列表，accumulate([1, 2, 3]) 会产生 [1, 3, 6]，也就是前缀和，但是通过增加参数 initial 的值可以改变初始前缀和值（该参数默认为 None），比如 accumulate([1, 2, 3], initial=0)，会在初始的地方增加一个 0，变成 [0, 1, 3, 6]；accumulate([1, 2, 3], initial=1)，就是 [1, 2, 4, 7]。代码解答（强烈建议自行解答后再看）参考题解 123456789class...

【Leetcode Daily】2559统计范围内的元音字符串数

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个字符串和一个二维整数数组，二维数组内每个元素有两个数值，代表一个区间，要求返回每个区间内开头和结尾都是元音字母的数量。思路分享基本前缀和的思路，可以参考【Leetcode Daily】303区域和检索-数组不可变除了题目，几乎与昨日的题目一模一样（【Leetcode Daily】3427变长子数组求和），故不做赘述。只补充一点感受，还真是有点不习惯这个 accumulate 函数，还是得慢慢适应这种有各种方便函数调用的 Python ~（蛇堕*n） https://leetcode.cn/problems/count-vowel-strings-in-ranges/solutions/2093978/suan-fa-xiao-ke-tang-qian-zhui-he-by-end-n0mx/ 代码解答（强烈建议自行解答后再看）参考题解 123456789101112131415161718class Solution: def vowelStrings(self, words:...

数据加载中