?LeetCode刷題實(shí)戰(zhàn)523：連續(xù)的子數(shù)組和
Given an integer array nums and an integer k, return true if nums has a continuous subarray of size at least two whose elements sum up to a multiple of k, or false otherwise.
An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.
子數(shù)組大小 至少為 2 ，且
子數(shù)組元素總和為 k 的倍數(shù)。
示例? ? ? ? ? ? ? ? ? ? ? ? ?
示例 1：
輸入：nums = [23,2,4,6,7], k = 6
輸出：true
解釋?zhuān)篬2,4] 是一個(gè)大小為 2?的子數(shù)組，并且和為 6?。
示例 2：
輸入：nums = [23,2,6,4,7], k = 6
輸出：true
解釋?zhuān)篬23, 2, 6, 4, 7] 是大小為 5?的子數(shù)組，并且和為 42?。
42?是 6?的倍數(shù)，因?yàn)?42?= 7?* 6?且 7?是一個(gè)整數(shù)。
示例 3：
輸入：nums = [23,2,6,4,7], k = 13
輸出：false
解題
class?Solution?{
public:
????bool?checkSubarraySum(vector<int>& nums, int?k)?{
????????int?len = nums.size();
????????if(k < 0)
????????????k = -k;
????????if(len < 2)
????????????return?false;
????????map<int,int> mp;
????????mp[0] = -1; // 處理數(shù)組和剛好能整除k的情況
????????int?rem = 0;
????????for(int?i = 0;i < len;i++){
????????????rem += nums[i];
????????????if(k) // 避免除數(shù)為0
????????????????rem = rem % k;
????????????if(mp.find(rem) != mp.end() ){
????????????????if(i - mp[rem] > 1)
????????????????????return?true;
????????????}
????????????else
????????????????mp[rem] = i;
???????????????????????
????????}
????????return?false;
????}
};