【算法题】1590. 使数组和能被 P 整除

程序员 · 2024-9-21 16:05:38

插：前些天发现了一个巨牛的人工智能学习网站，平凡易懂，风趣幽默，不由得分享一下给各人。点击跳转到网站。
坚固不拔，越积极越荣幸，各人一起学习鸭~~~

标题：

给你一个正整数数组 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 <= 10^9
1 <= p <= 10^9
java代码：

class Solution { public int minSubarray(int[] nums, int p) { int mod = 0; for (int num : nums) { mod = (mod + num) % p; } if (mod == 0) { return 0; } int ans = Integer.MAX_VALUE; Map<Integer, Integer> map = new HashMap<>(); map.put(0, -1); for (int i = 0, sum = 0; i < nums.length; i++) { sum = (sum + nums) % p; int find = (sum - mod + p) % p; if (map.containsKey(find)) { ans = Math.min(ans, i - map.get(find)); } map.put(sum, i); } return ans == Integer.MAX_VALUE || ans == nums.length ? -1 : ans; }}

【算法题】1590. 使数组和能被 P 整除

所属分类: 问答交流

新帖推荐: 30日

推荐作品