2023-07-18：给你一个正整数数组 nums，请你移除 最短 子数组（可以为 空），
使得剩余元素的 和 能被 p 整除。 不允许 将整个数组都移除。
请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。
子数组 定义为原数组中连续的一组元素。
输入：nums = [3,1,4,2], p = 6。
输出：1。
答案2023-07-18：
大体过程如下：
1.计算整个数组的和对p取余，得到allMod。
2.初始化一个空的映射m，并将映射中键为0，值为-1。该映射用于记录前缀和的某个余数最晚出现的位置。
3.初始化一个变量ans，表示最短子数组的长度，初值为无穷大。
4.初始化一个变量curMod，表示当前的前缀和余数，初值为0。
5.初始化一个变量find，表示要查找的余数，初值为0。
6.遍历数组nums中的每个元素：
-
将当前元素加到
curMod中，并对p取余，得到当前前缀和的余数curMod。 -
计算要查找的余数
find = (curMod - allMod + p) % p。 -
在映射
m中查找余数为find的键，如果存在则计算当前位置与查找到的位置之差，并更新ans为较小的值。 -
更新映射
m，将当前余数curMod存储到映射中。
7.如果ans没有被更新，则返回-1，否则返回ans。
代码的时间复杂度为O(n)，其中n是数组nums的长度。这是因为在遍历数组nums的过程中，需要进行常数时间的操作，包括计算前缀和的余数、更新映射m等。
代码的空间复杂度为O(n)，其中n是数组nums的长度。这是因为需要使用一个映射m来记录前缀和的余数及其最晚出现的位置，映射m的大小不会超过数组的长度n。此外，还需要用几个额外的变量来存储一些中间结果，这些变量的空间占用也是常数级别的，不会随着输入规模n的增大而增加。
go完整代码如下：
package main
import (
"fmt"
)
func minSubarray(nums []int, p int) int {
n := len(nums)
// 求出整体的余数
allMod := 0
for _, num := range nums {
allMod = (allMod + num) % p
}
if allMod == 0 {
return 0
}
// 记录前缀和的某个余数，最晚出现的位置
// 看课！然后看接下来的代码
m := make(map[int]int)
m[0] = -1
ans := 1<<31 - 1
curMod := 0
var find int
for i := 0; i < n; i++ {
// 0...i 累加和的余数
curMod = (curMod + nums[i]) % p
// 如果p = 7，整体余数2，当前余数5，那么找之前的部分余数是3
// 如果p = 7，整体余数2，当前余数1，那么找之前的部分余数是6
// 整体变成下面的公式，可以自己带入各种情况验证
find = (curMod - allMod + p) % p
val, ok := m[find]
if ok {
if i != n-1 || val != -1 {
// 防止删掉整体！
// ...i(n-1)
ans = min(ans, i-val)
}
}
m[curMod] = i
}
if ans == 1<<31-1 {
return -1
}
return ans
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func main() {
nums := []int{3, 1, 4, 2}
p := 6
result := minSubarray(nums, p)
fmt.Println(result)
}
rust代码如下：
use std::collections::HashMap;
fn min_subarray(nums: Vec<i32>, p: i32) -> i32 {
let n = nums.len();
// 求出整体的余数
let all_mod: i32 = nums.iter().sum::<i32>() % p;
if all_mod == 0 {
return 0;
}
// 记录前缀和的某个余数，最晚出现的位置
let mut map: HashMap<i32, i32> = HashMap::new();
map.insert(0, -1);
let mut ans = i32::max_value();
let mut cur_mod = 0;
let mut find;
for i in 0..n {
// 0...i 累加和的余数
cur_mod = (cur_mod + nums[i]) % p;
// 如果p = 7，整体余数2，当前余数5，那么找之前的部分余数是3
// 如果p = 7，整体余数2，当前余数1，那么找之前的部分余数是6
// 整体变成下面的公式，可以自己带入各种情况验证
find = (cur_mod - all_mod + p) % p;
if map.contains_key(&find) {
if i != n - 1 || map[&find] != -1 {
// 防止删掉整体！
// ...i(n-1)
ans = ans.min(i as i32 - map[&find]);
}
}
map.insert(cur_mod, i as i32);
}
return if ans == i32::max_value() { -1 } else { ans };
}
fn main() {
let nums = vec![3, 1, 4, 2];
let p = 6;
let result = min_subarray(nums, p);
println!("{}", result);
}
c++完整代码如下：
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int minSubarray(vector<int>& nums, int p) {
int n = nums.size();
// 求出整体的余数
int allMod = 0;
for (int num : nums) {
allMod = (allMod + num) % p;
}
if (allMod == 0) {
return 0;
}
// 记录前缀和的某个余数，最晚出现的位置
// 看课！然后看接下来的代码
unordered_map<int, int> map;
map[0] = -1;
int ans = INT_MAX;
int curMod = 0, find;
for (int i = 0; i < n; i++) {
// 0...i 累加和的余数
curMod = (curMod + nums[i]) % p;
// 如果p = 7，整体余数2，当前余数5，那么找之前的部分余数是3
// 如果p = 7，整体余数2，当前余数1，那么找之前的部分余数是6
// 整体变成下面的公式，可以自己带入各种情况验证
find = (curMod - allMod + p) % p;
if (map.find(find) != map.end()) {
if (i != n - 1 || map[find] != -1) {
// 防止删掉整体！
// ...i(n-1)
ans = min(ans, i - map[find]);
}
}
map[curMod] = i;
}
return (ans == INT_MAX) ? -1 : ans;
}
int main() {
vector<int> nums = { 3, 1, 4, 2 };
int p = 6;
int result = minSubarray(nums, p);
cout << "Result: " << result << endl;
return 0;
}
c完整代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int minSubarray(int* nums, int numsSize, int p) {
int n = numsSize;
// 求出整体的余数
int allMod = 0;
for (int i = 0; i < n; i++) {
allMod = (allMod + nums[i]) % p;
}
if (allMod == 0) {
return 0;
}
// 记录前缀和的某个余数，最晚出现的位置
// 看课！然后看接下来的代码
int* map = (int*)malloc(sizeof(int) * p);
for (int i = 0; i < p; i++) {
map[i] = -1;
}
map[0] = -1;
int ans = INT_MAX;
int curMod = 0, find;
for (int i = 0; i < n; i++) {
// 0...i 累加和的余数
curMod = (curMod + nums[i]) % p;
// 如果p = 7，整体余数2，当前余数5，那么找之前的部分余数是3
// 如果p = 7，整体余数2，当前余数1，那么找之前的部分余数是6
// 整体变成下面的公式，可以自己带入各种情况验证
find = (curMod - allMod + p) % p;
if (map[find] != -1) {
if (i != n - 1 || map[find] != -1) {
// 防止删掉整体！
// ...i(n-1)
ans = (ans < i - map[find]) ? ans : i - map[find];
}
}
map[curMod] = i;
}
free(map);
return (ans == INT_MAX) ? -1 : ans;
}
int main() {
int nums[] = { 3, 1, 4, 2 };
int p = 6;
int numsSize = sizeof(nums) / sizeof(nums[0]);
int result = minSubarray(nums, numsSize, p);
printf("Result: %d\n", result);
return 0;
}
