1590. 使数组和能被 P 整除

🟠   🔖  数组 哈希表 前缀和  🔗 力扣 LeetCode

题目

Given an array of positive integers nums, remove the smallest subarray (possibly empty ) such that the sum of the remaining elements is divisible by p. It is not allowed to remove the whole array.

Return the length of the smallest subarray that you need to remove, or-1if it 's impossible.

A subarray is defined as a contiguous block of elements in the array.

Example 1:

Input: nums = [3,1,4,2], p = 6

Output: 1

Explanation: The sum of the elements in nums is 10, which is not divisible by 6. We can remove the subarray [4], and the sum of the remaining elements is 6, which is divisible by 6.

Example 2:

Input: nums = [6,3,5,2], p = 9

Output: 2

Explanation: We cannot remove a single element to get a sum divisible by 9. The best way is to remove the subarray [5,2], leaving us with [6,3] with sum 9.

Example 3:

Input: nums = [1,2,3], p = 3

Output: 0

Explanation: Here the sum is 6. which is already divisible by 3. Thus we do not need to remove anything.

Constraints:

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

题目大意

给你一个正整数数组 nums，请你移除 最短 子数组（可以为 空），使得剩余元素的 和 能被 p 整除。 不允许 将整个数组都移除。

请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。

子数组 定义为原数组中连续的一组元素。

解题思路

1. 计算总和：

   • 使用 reduce 方法计算数组 nums 的总和，并将其存储在变量 sum 中。

2. 确定总余数：

   • 计算 totalRemainder 为 sum % p。如果 totalRemainder 为 0，说明整个数组的和已经可以被 p 整除，因此直接返回 0，因为不需要移除任何元素。

3. 初始化变量：

   • 创建一个哈希表 map，用于存储遇到的余数及其对应的索引。初始化时将 {0: -1} 放入其中，以处理可能需要从数组开头移除元素的情况。
   • 初始化 curRemainder 为 0，用于在遍历数组时存储当前累积和的余数。
   • 将 res 设置为数组的长度 (nums.length)，用于跟踪需要移除的最小子数组长度。

4. 遍历数组：

   • 遍历数组，更新当前和的余数。对于每个元素，检查是否存在一个以前的余数，使得 curRemainder - totalRemainder 可以被 p 整除。
   • 如果找到，计算需要移除的子数组的长度，并更新最小长度。
   • 将当前的 curRemainder 和其索引 i 存入哈希表，以便后续使用。

5. 返回结果：

   • 遍历结束后，检查 res 是否仍等于数组的长度。如果是，返回 -1，表示无法找到合适的子数组；否则，返回 res 的值，表示需要移除的最小子数组长度。

复杂度分析

• 时间复杂度：O(n)，需要遍历数组一次。
• 空间复杂度：O(n)，用于存储哈希表。

代码

/**
 * @param {number[]} nums
 * @param {number} p
 * @return {number}
 */
var minSubarray = function (nums, p) {
	const sum = nums.reduce((a, b) => a + b, 0);
	const totalRemainder = sum % p;
	// 如果总和已经可以被 p 整除，直接返回 0
	if (totalRemainder == 0) return 0;

	let map = new Map(),
		curRemainder = 0,
		res = nums.length;

	// 处理边界情况
	map.set(0, -1);

	for (let i = 0; i < nums.length; i++) {
		// 计算当前的余数
		curRemainder = (curRemainder + nums[i]) % p;
		// 计算需要的余数
		const targetRemainder = (curRemainder - totalRemainder + p) % p;
		// 如果存在这样的余数
		if (map.has(targetRemainder)) {
			res = Math.min(res, i - map.get(targetRemainder));
		}
		// 记录当前余数及其索引
		map.set(curRemainder, i);
	}
	// 如果没有找到，返回 -1
	return res == nums.length ? -1 : res;
};

相关题目

题号	标题	题解	标签	难度
974	和可被 K 整除的子数组		数组 哈希表 前缀和
2575	找出字符串的可整除数组		数组 数学 字符串