class Solution {
public:
int minSubarray(vector<int>& nums, int p) {
}
};
1590. 使数组和能被 P 整除
给你一个正整数数组 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 <= 1051 <= nums[i] <= 1091 <= p <= 109原站题解
python3 解法, 执行用时: 148 ms, 内存消耗: 35.4 MB, 提交时间: 2023-03-10 09:13:35
class Solution:
def minSubarray(self, nums: List[int], p: int) -> int:
x = sum(nums) % p
if x == 0: return 0 # 移除空子数组（这行可以不要）
ans = n = len(nums)
s = 0
last = {s: -1} # 由于下面 i 是从 0 开始的，前缀和下标就要从 -1 开始了
for i, v in enumerate(nums):
s += v
last[s % p] = i
j = last.get((s - x) % p, -n) # 如果不存在，-n 可以保证 i-j >= n
ans = min(ans, i - j) # 改成手写 min 会再快一些
return ans if ans < n else -1
java 解法, 执行用时: 24 ms, 内存消耗: 61.7 MB, 提交时间: 2023-03-10 09:13:06
class Solution {
public int minSubarray(int[] nums, int p) {
long t = 0;
for (int v : nums) t += v;
int x = (int) (t % p);
if (x == 0) return 0; // 移除空子数组（这行可以不要）
int n = nums.length, ans = n, s = 0;
var last = new HashMap<Integer, Integer>(); // 注：填入 n+1 可以加速
last.put(s, -1); // 由于下面 i 是从 0 开始的，前缀和下标就要从 -1 开始了
for (int i = 0; i < n; ++i) {
s = (s + nums[i]) % p;
last.put(s, i);
// 如果不存在，-n 可以保证 i-j >= n
int j = last.getOrDefault((s - x + p) % p, -n);
ans = Math.min(ans, i - j);
}
return ans < n ? ans : -1;
}
}
golang 解法, 执行用时: 104 ms, 内存消耗: 12.9 MB, 提交时间: 2023-03-10 09:12:53
func minSubarray(nums []int, p int) int {
x := 0
for _, v := range nums {
x += v
}
x %= p
if x == 0 {
return 0 // 移除空子数组（这个 if 可以不要）
}
n := len(nums)
ans, s := n, 0
// 由于下面 i 是从 0 开始的，前缀和下标就要从 -1 开始了
last := map[int]int{s: -1}
for i, v := range nums {
s += v
last[s%p] = i
if j, ok := last[(s-x+p)%p]; ok {
ans = min(ans, i-j)
}
}
if ans < n {
return ans
}
return -1
}
func min(a, b int) int { if b < a { return b }; return a }
golang 解法, 执行用时: 96 ms, 内存消耗: 12.3 MB, 提交时间: 2023-03-10 09:12:34
func minSubarray(nums []int, p int) int {
n := len(nums)
s := make([]int, n+1)
for i, v := range nums {
s[i+1] = (s[i] + v) % p
}
x := s[n]
if x == 0 {
return 0 // 移除空子数组（这个 if 可以不要）
}
ans := n
last := map[int]int{}
for i, v := range s {
last[v] = i
if j, ok := last[(v-x+p)%p]; ok {
ans = min(ans, i-j)
}
}
if ans < n {
return ans
}
return -1
}
func min(a, b int) int { if b < a { return b }; return a }
java 解法, 执行用时: 33 ms, 内存消耗: 62.7 MB, 提交时间: 2023-03-10 09:10:57
class Solution {
public int minSubarray(int[] nums, int p) {
int n = nums.length, ans = n;
var s = new int[n + 1];
for (int i = 0; i < n; ++i)
s[i + 1] = (s[i] + nums[i]) % p;
int x = s[n];
if (x == 0) return 0; // 移除空子数组（这行可以不要）
var last = new HashMap<Integer, Integer>();
for (int i = 0; i <= n; ++i) {
last.put(s[i], i);
// 如果不存在，-n 可以保证 i-j >= n
int j = last.getOrDefault((s[i] - x + p) % p, -n);
ans = Math.min(ans, i - j);
}
return ans < n ? ans : -1;
}
}
python3 解法, 执行用时: 140 ms, 内存消耗: 40.2 MB, 提交时间: 2023-03-10 09:10:30
'''
前缀和 + 哈希
'''
class Solution:
def minSubarray(self, nums: List[int], p: int) -> int:
s = list(accumulate(nums, initial=0)) # 前缀和
x = s[-1] % p
if x == 0: return 0 # 移除空子数组（这行可以不要）
ans = n = len(nums)
last = {}
for i, v in enumerate(s):
last[v % p] = i
j = last.get((v - x) % p, -n) # 如果不存在，-n 可以保证 i-j >= n
ans = min(ans, i - j)
return ans if ans < n else -1