使数组和能被 P 整除

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 -1 if 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 <= 105
• 1 <= nums[i] <= 109
• 1 <= p <= 109

/*
 * 思路：
 * 使用Java Stream API来计算数组总和，并利用传统循环和HashMap来处理前缀和的模运算。
 */
import java.util.HashMap;
import java.util.stream.IntStream;

public class SolutionStream {
    public int minSubarray(int[] nums, int p) {
        int totalSum = IntStream.of(nums).sum();
        int target = totalSum % p;
        if (target == 0) return 0;
        HashMap<Integer, Integer> prefixMod = new HashMap<>();
        prefixMod.put(0, -1);
        int prefixSum = 0, minLen = nums.length;
        for (int i = 0; i < nums.length; i++) {
            prefixSum += nums[i];
            int currentMod = prefixSum % p;
            int requiredMod = (currentMod - target + p) % p;
            if (prefixMod.containsKey(requiredMod)) {
                minLen = Math.min(minLen, i - prefixMod.get(requiredMod));
            }
            prefixMod.put(currentMod, i);
        }
        return minLen == nums.length ? -1 : minLen;
    }
}

题解采用了前缀和与哈希表来解决问题。首先，计算数组总和的余数 k（与 p 的余数），如果 k 为 0，则整个数组和已经是 p 的倍数，直接返回 0。如果 k 不为 0，需要找到一个最短的子数组，移除后剩余部分的和为 p 的倍数。通过逐步构建前缀和，并计算每一步的余数 y 存储到哈希表中（键为余数，值为对应的索引）。为了找到符合条件的子数组，计算每个位置的前缀和余数 x，它是将当前余数调整到我们需要的余数。如果这个 x 出现在哈希表中，则说明从该位置到当前位置的子数组是一个候选子数组。通过比较和更新最小长度，最终得到结果。

O(n)

O(n)