523

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.

以下代码是参考leetcode上的。

DP.

设这个数组是a1a2...an, sum[i]=a1+...ai(sum[i]只是用来说明)。要判断数组中某一段连续子序列（长度>=2）是否能被k整除，我们只需判断sum[i]%k=sum[j]%k（i<j且j-i>=2），如果找到这样的两个位置的sum，则说明i+1,i+2,...,j就构成一个我们想要的连续子序列。这是核心想法。

尤其要注意>=2这个条件。我们这里采用pre,延后了每一个位置的判定。在每一个位置，我们采用先检查后插入的形式，而且插入的东西是前一个位置sum的模值。第一个元素是不用检查的，因为只有一个元素，实际上也没法检查（因为set中没东西）。但是我们巧妙地插入了一个0作为mod0（mod数组即为每个位置的sum的模值），这样一来从第二个元素开始就可以判断了。这样做的结果就是：第一个元素不检查，第二个元素检查mod0,第三个元素检查mod0,mod1...第n个元素检查mod0,mod1,...,mod(n-2)。一旦要检查的序列中有一个值与当前的mod值相等，则说明true。

用了stl里的unordered_set，不是用红黑树而是用哈希表实现的，还是要学习一个。

 1 class Solution {
 2 public:
 3     bool checkSubarraySum(vector<int>& nums, int k) {
 4         int n=nums.size(),pre=0,sum=0;
 5         unordered_set<int>mod_k;
 6         for(int i=0;i<n;i++)
 7         {
 8             sum+=nums[i];
 9             int mod=k==0?sum:sum%k;
10             if(mod_k.count(mod))
11                 return true;
12             mod_k.insert(pre);
13             pre=mod;
14         }
15         return false;
16     }
17 };