题目地址：https://leetcode.com/PRoblems/continuous-subarray-sum/?tab=Description
题目描述：Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.
我的代码：
class Solution {public: bool checkSubarraySum(vector<int>& nums, int k) { int n=nums.size(); if(k==0){ for(int i=0;i<n-1;i++){ if(nums[i]==0) if(nums[i+1]==0) return true; } return false; } else if(k<0) k=0-k; vector<long> sums; sums.push_back(0); for(int i=0;i<n;i++) sums.push_back(sums[i]+nums[i]); map<int,int> exist; for(int i=1;i<=n;i++){ int m=sums[i]%k; if(m==0&&i!=1) return true; if(exist.count(m)==0) exist[m]=i; else if(exist[m]!=i-1) return true; } return false; }};解题思路： 题目要求判断是否有两个或两个以上连续数之和被k整除。 若直接计算所有可能情况，复杂度为O(n^2)。 但此处可利用整除的性质，将数组的前i个数之和用sum保存，如此，任意连续多个数之和都可以表示成sum中不相邻的两个数之差。 而k整除两数之差即等同于两数模k同余。 所有依次对sum模k，并保存在map中，若该结果已在之前不相邻的数中出现过，则返回true。 但有两点需要注意，一方面是当k为0时，不可能模k取余，需特殊处理。令一方面当模k余0时，可直接获得结论，当然这总情况可以通过添加sum[0]=0模k余0来做一般化处理。
新闻热点
疑难解答
