1590. Make Sum Divisible by P

题目信息

题号:

1590

难度:

Medium

主题:

数组、前缀和、模运算、哈希表

原题:

LeetCode 1590

重点:

删除一个连续子数组后使剩余总和能被 p 整除;不能删除整个数组,求最短长度

题目重述

给定正整数数组 nums 和正整数 p。可以删除一个连续子数组,也可以不删除,使剩余元素总和能够被 p 整除。

请返回需要删除的最短子数组长度。禁止删除整个数组;若无法满足条件,返回 -1。

1 <= nums.length <= 10^5,1 <= nums[i] <= 10^9,1 <= p <= 10^9。

自建示例

删除一个余数匹配的单元素即可:

输入:nums = [3,1,4,2], p = 6
输出:1
解释:总和为 10,删除元素 4 后剩余和为 6。

总和已经整除时无需删除:

输入:nums = [1,2,3], p = 3
输出:0
解释:数组总和 6 已能被 3 整除。