福千欣隆网站建设公司怎么样,长春seo公司网站,无锡企业网银,saas 做网站LeetCode-1590. 使数组和能被 P 整除【前缀和#xff0c;哈希表】题目描述#xff1a;解题思路一#xff1a;前缀和#xff0c;具体看注释。解题思路二#xff1a;在遍历过程中计算前缀和解题思路三#xff1a;0题目描述#xff1a;
给你一个正整数数组 nums#xff0…
LeetCode-1590. 使数组和能被 P 整除【前缀和哈希表】题目描述解题思路一前缀和具体看注释。解题思路二在遍历过程中计算前缀和解题思路三0题目描述
给你一个正整数数组 nums请你移除 最短 子数组可以为 空使得剩余元素的 和 能被 p 整除。 不允许 将整个数组都移除。
请你返回你需要移除的最短子数组的长度如果无法满足题目要求返回 -1 。
子数组 定义为原数组中连续的一组元素。
示例 1
输入nums [3,1,4,2], p 6 输出1 解释nums 中元素和为 10不能被 p 整除。我们可以移除子数组 [4] 剩余元素的和为 6 。
示例 2
输入nums [6,3,5,2], p 9 输出2 解释我们无法移除任何一个元素使得和被 9 整除最优方案是移除子数组 [5,2] 剩余元素为 [6,3]和为 9 。
示例 3
输入nums [1,2,3], p 3 输出0 解释和恰好为 6 已经能被 3 整除了。所以我们不需要移除任何元素。
示例 4
输入nums [1,2,3], p 7 输出-1 解释没有任何方案使得移除子数组后剩余元素的和被 7 整除。
示例 5
输入nums [1000000000,1000000000,1000000000], p 3 输出0
提示
1 nums.length 10^5 1 nums[i] 10^9 1 p 10^9 https://leetcode.cn/problems/make-sum-divisible-by-p/description/
解题思路一前缀和具体看注释。
class Solution:def minSubarray(self, nums: List[int], p: int) - int:slist(accumulate(nums,initial0)) #直接求前缀和xs[-1]%p #数组所有元素的和对p取余if x0: return 0 #直接返回ansnlen(nums)last{}for i,v in enumerate(s):#当前前缀和是v,我们找(v-y)%px其中的前缀和为y的坐标#因为取余的性质y%p(v-x)%p。我们仅需找到满足其最大的地址即可last[v%p]i #key是当前前缀和取余之后的数value是地址jlast.get((v-x)%p,-n)#如果key不存在-n可以保证i-jnansmin(ans,i-j)return ans if ansn else -1
时间复杂度O(n) 空间复杂度O(n)//哈希表
解题思路二在遍历过程中计算前缀和
last{s:-1}是将key:value赋值给last字典
class Solution:def minSubarray(self, nums: List[int], p: int) - int:xsum(nums)%p #数组所有元素的和对p取余if x0: return 0 #直接返回ansnlen(nums)s0last{s:-1}# 由于下面 i 是从 0 开始的前缀和下标就要从 -1 开始了for i,v in enumerate(nums):#当前前缀和是v,我们找(v-y)%px其中的前缀和为y的坐标#因为取余的性质y%p(v-x)%p。我们仅需找到满足其最大的地址即可svlast[s%p]i #key是当前前缀和取余之后的数value是地址jlast.get((s-x)%p,-n)#如果key不存在-n可以保证i-jnansmin(ans,i-j)return ans if ansn else -1时间复杂度O(n) 空间复杂度O(n)//哈希表
解题思路三0
