给你一个长度为 n 的整数数组 nums 和一个整数 p，请你选出一个 非空 的子数组使得该子数组元素和对 p 的余数是 0，但不能选出全部元素。
计算这个子数组的长度，如果不存在这样的子数组，返回 -1。
一个数组的 子数组 定义为一个由数组中零个或者更多个连续元素组成的数组。
示例 1：
输入：nums = [3,1,4,2], p = 6 输出：1 解释：我们选出数列中的一个数字 4，使得它和剩下的数的和等于 6。
示例 2：
输入：nums = [6,3,5,2], p = 9 输出：2 解释：我们选出前两个数字，它们的和为 9，但它们不是整个数组的和。
示例 3：
输入：nums = [1,2,3], p = 3 输出：0 解释：这个数组本身就可以被 3 整除。
示例 4：
输入：nums = [1,2,3], p = 7 输出：-1 解释：没有任何子数组满足题意。
提示：
1 <= n <= 10^51 <= nums[i] <= 10^91 <= p <= 10^9
解法
首先求出 nums 中所有元素的和 sum，如果 sum % p == 0，则整个数组就是一个符合要求的子数组，返回 0 即可。
如果 sum % p != 0，我们需要找到一个子数组，使得它的和对 p 取模等于 sum % p。我们可以用前缀和的方法来做。
具体来说，我们维护一个前缀和数组 prefix，其中 prefix[i] 表示 nums 中前 i 项的和。然后我们枚举右端点 i，左端点设为 j，判断子数组 nums[j..i] 的和是否等于 sum % p。如果等于，记录子数组长度和当前最小长度的较小值。如果不等于，继续枚举，直到找到符合要求的子数组或者枚举完所有子数组。
为了加速查找，我们可以使用哈希表来存储每个前缀和对 p 取模后的值以及对应的下标。在枚举右端点时，我们只需要查询哈希表中是否存在对应的前缀和即可。
代码实现
public int minSubarray(int[] nums, int p) {
int len = nums.length;
int mod = 0;
for (int n : nums) {
mod = (mod + n) % p;
}
if (mod == 0) {
return 0;
}
int ans = Integer.MAX_VALUE;
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
int sum = 0;
for (int i = 0; i < len; i++) {
sum = (sum + nums[i])%p;
int gap = (sum - mod + p) % p;
if (map.containsKey(gap)) {
ans = Math.min(i - map.get(gap), ans);
}
map.put(sum, i);
}
return ans == len || ans == Integer.MAX_VALUE ? -1 : ans;
}
时间复杂度：O(n)
空间复杂度：O(n)