LeetCode-1590. 使数组和能被 P 整除【前缀和,哈希表】
2023-09-14 09:01:27 时间
LeetCode-1590. 使数组和能被 P 整除【前缀和,哈希表】
题目描述:
给你一个正整数数组 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:
s=list(accumulate(nums,initial=0)) #直接求前缀和
x=s[-1]%p #数组所有元素的和对p取余
if x==0: return 0 #直接返回
ans=n=len(nums)
last={}
for i,v in enumerate(s):
#当前前缀和是v,我们找(v-y)%p=x其中的前缀和为y的坐标
#因为取余的性质,y%p=(v-x)%p。我们仅需找到满足其最大的地址即可
last[v%p]=i #key是当前前缀和取余之后的数,value是地址
j=last.get((v-x)%p,-n)#如果key不存在,-n可以保证i-j>=n
ans=min(ans,i-j)
return ans if ans<n else -1
时间复杂度:O(n)
空间复杂度:O(n)//哈希表
解题思路二:在遍历过程中计算前缀和
last={s:-1}
是将key:value赋值给last字典
class Solution:
def minSubarray(self, nums: List[int], p: int) -> int:
x=sum(nums)%p #数组所有元素的和对p取余
if x==0: return 0 #直接返回
ans=n=len(nums)
s=0
last={s:-1}# 由于下面 i 是从 0 开始的,前缀和下标就要从 -1 开始了
for i,v in enumerate(nums):
#当前前缀和是v,我们找(v-y)%p=x其中的前缀和为y的坐标
#因为取余的性质,y%p=(v-x)%p。我们仅需找到满足其最大的地址即可
s+=v
last[s%p]=i #key是当前前缀和取余之后的数,value是地址
j=last.get((s-x)%p,-n)#如果key不存在,-n可以保证i-j>=n
ans=min(ans,i-j)
return ans if ans<n else -1
时间复杂度:O(n)
空间复杂度:O(n)//哈希表
解题思路三:0
相关文章
- ☆打卡算法☆LeetCode 207. 课程表 算法解析
- ☆打卡算法☆LeetCode 219. 存在重复元素 II 算法解析
- ☆打卡算法☆LeetCode 224. 基本计算器 算法解析
- ☆打卡算法☆LeetCode 225. 用队列实现栈 算法解析
- [LeetCode]238. 除自身以外数组的乘积
- Leetcode 差分数组的应用「建议收藏」
- LeetCode 算法题系列(第一周 25道)
- 《三战Leetcode》寻找有序数组的中位数
- ☆打卡算法☆LeetCode 188. 轮转数组 算法解析
- LeetCode周赛304,图论双压,你能搞定吗?
- leetcode-189. 旋转数组
- leetcode-88合并两个有序数组(双指针)
- Leetcode 题目002-用链表实现大数加法
- LeetCode 7. 整数反转
- LeetCode 2197. 替换数组中的非互质数(栈)
- 【leetcode速通java版】01——数组入门
- JavaScript刷LeetCode拿offer-滑动窗口
- leetcode 记录
- LeetCode 1236/1242 设计一个(多线程)爬虫解法
- LeetCode题解——数组篇
- 前端工程师leetcode算法面试必备-二叉树的构造和遍历1
- 前端工程师leetcode算法面试必备-简单的二叉树
- JavaScript刷LeetCode-字符串类解题技巧4
- LeetCode-16-最接近的三数之和
- Leetcode 560. 和为 K 的子数组
- LeetCode | 爬楼梯
- 【Leetcode-链表强训】
- LeetCode 复制带随机指针的链表(C语言)
- 每日一道leetcode:4. 寻找两个正序数组的中位数