2023-07-18：給你一個正整數(shù)數(shù)組 nums，請你移除 最短 子數(shù)組（可以為 空）， 使得剩
2023-07-18：給你一個正整數(shù)數(shù)組 nums，請你移除 最短 子數(shù)組（可以為 空），
使得剩余元素的 和 能被 p 整除。 不允許 將整個數(shù)組都移除。
請你返回你需要移除的最短子數(shù)組的長度，如果無法滿足題目要求，返回 -1 。
子數(shù)組 定義為原數(shù)組中連續(xù)的一組元素。
輸入：nums = [3,1,4,2], p = 6。
輸出：1。
答案2023-07-18：
大體過程如下：
1.計(jì)算整個數(shù)組的和對p取余，得到allMod。
2.初始化一個空的映射m，并將映射中鍵為0，值為-1。該映射用于記錄前綴和的某個余數(shù)最晚出現(xiàn)的位置。
3.初始化一個變量ans，表示最短子數(shù)組的長度，初值為無窮大。
4.初始化一個變量curMod，表示當(dāng)前的前綴和余數(shù)，初值為0。
5.初始化一個變量find，表示要查找的余數(shù)，初值為0。
6.遍歷數(shù)組nums中的每個元素：
??將當(dāng)前元素加到
curMod中，并對p取余，得到當(dāng)前前綴和的余數(shù)curMod。??計(jì)算要查找的余數(shù)
find = (curMod - allMod + p) % p。??在映射
m中查找余數(shù)為find的鍵，如果存在則計(jì)算當(dāng)前位置與查找到的位置之差，并更新ans為較小的值。??更新映射
m，將當(dāng)前余數(shù)curMod存儲到映射中。
7.如果ans沒有被更新，則返回-1，否則返回ans。
代碼的時間復(fù)雜度為O(n)，其中n是數(shù)組nums的長度。這是因?yàn)樵诒闅v數(shù)組nums的過程中，需要進(jìn)行常數(shù)時間的操作，包括計(jì)算前綴和的余數(shù)、更新映射m等。
代碼的空間復(fù)雜度為O(n)，其中n是數(shù)組nums的長度。這是因?yàn)樾枰褂靡粋€映射m來記錄前綴和的余數(shù)及其最晚出現(xiàn)的位置，映射m的大小不會超過數(shù)組的長度n。此外，還需要用幾個額外的變量來存儲一些中間結(jié)果，這些變量的空間占用也是常數(shù)級別的，不會隨著輸入規(guī)模n的增大而增加。
go完整代碼如下：
package?main
import?(
????"fmt"
)
func?minSubarray(nums?[]int,?p?int)?int?{
????n?:=?len(nums)
????//?求出整體的余數(shù)
????allMod?:=?0
????for?_,?num?:=?range?nums?{
????????allMod?=?(allMod?+?num)?%?p
????}
????if?allMod?==?0?{
????????return?0
????}
????//?記錄前綴和的某個余數(shù)，最晚出現(xiàn)的位置
????//?看課！然后看接下來的代碼
????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?累加和的余數(shù)
????????curMod?=?(curMod?+?nums[i])?%?p
????????//?如果p?=?7，整體余數(shù)2，當(dāng)前余數(shù)5，那么找之前的部分余數(shù)是3
????????//?如果p?=?7，整體余數(shù)2，當(dāng)前余數(shù)1，那么找之前的部分余數(shù)是6
????????//?整體變成下面的公式，可以自己帶入各種情況驗(yàn)證
????????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();
????
????//?求出整體的余數(shù)
????let?all_mod:?i32?=?nums.iter().sum::<i32>()?%?p;
????if?all_mod?==?0?{
????????return?0;
????}
????
????//?記錄前綴和的某個余數(shù)，最晚出現(xiàn)的位置
????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?累加和的余數(shù)
????????cur_mod?=?(cur_mod?+?nums[i])?%?p;
????????
????????//?如果p?=?7，整體余數(shù)2，當(dāng)前余數(shù)5，那么找之前的部分余數(shù)是3
????????//?如果p?=?7，整體余數(shù)2，當(dāng)前余數(shù)1，那么找之前的部分余數(shù)是6
????????//?整體變成下面的公式，可以自己帶入各種情況驗(yàn)證
????????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++完整代碼如下：
using?namespace?std;
int?minSubarray(vector<int>&?nums,?int?p)?{
????int?n?=?nums.size();
????//?求出整體的余數(shù)
????int?allMod?=?0;
????for?(int?num?:?nums)?{
????????allMod?=?(allMod?+?num)?%?p;
????}
????if?(allMod?==?0)?{
????????return?0;
????}
????//?記錄前綴和的某個余數(shù)，最晚出現(xiàn)的位置
????//?看課！然后看接下來的代碼
????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?累加和的余數(shù)
????????curMod?=?(curMod?+?nums[i])?%?p;
????????//?如果p?=?7，整體余數(shù)2，當(dāng)前余數(shù)5，那么找之前的部分余數(shù)是3
????????//?如果p?=?7，整體余數(shù)2，當(dāng)前余數(shù)1，那么找之前的部分余數(shù)是6
????????//?整體變成下面的公式，可以自己帶入各種情況驗(yàn)證
????????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完整代碼如下：
int?minSubarray(int*?nums,?int?numsSize,?int?p)?{
????int?n?=?numsSize;
????//?求出整體的余數(shù)
????int?allMod?=?0;
????for?(int?i?=?0;?i?<?n;?i++)?{
????????allMod?=?(allMod?+?nums[i])?%?p;
????}
????if?(allMod?==?0)?{
????????return?0;
????}
????//?記錄前綴和的某個余數(shù)，最晚出現(xiàn)的位置
????//?看課！然后看接下來的代碼
????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?累加和的余數(shù)
????????curMod?=?(curMod?+?nums[i])?%?p;
????????//?如果p?=?7，整體余數(shù)2，當(dāng)前余數(shù)5，那么找之前的部分余數(shù)是3
????????//?如果p?=?7，整體余數(shù)2，當(dāng)前余數(shù)1，那么找之前的部分余數(shù)是6
????????//?整體變成下面的公式，可以自己帶入各種情況驗(yàn)證
????????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;
}
