这道题的简单版是求子数列的和的最大值，一般的做法是做动态规划，或者用两个指针指示子数列前后，和一个int来存当前已知的最大值，最后遍历一次数组就能解决了。这次变得困难了一些。是求是否存在一个子数列的和是给定非负整数k的整数倍。毫无思路，后来看了一下讨论。感觉清晰多了，整理如下：
时间复杂度是O(n^2)，空间复杂度是O(n)。运行时间大概会用到将近160ms（Ac边缘），很暴力，就是算出所有可能，然后一个个可能去判断是否是k的倍数。最后有个特殊边界是0，0和k=0的情况。
public boolean checkSubarraySum(int[] nums, int k) { if (nums.length < 2) return false; if (k == 0) { for (int i = 0; i < nums.length - 1; i++) { if (nums[i] == 0 && nums[i + 1] == 0) return true; } return false; } int[] dp = Arrays.copyOf(nums, nums.length); for (int i = 1; i < nums.length; i++) { for (int j = 0; j < nums.length - i; j++) { dp[j] += nums[j + i]; if (dp[j] % k == 0) return true; } } return false;}只需要历遍数组一次，计算runningSum的大小，一旦出现两个一样的runningSum而且中间相隔1个以上的数字，那么之间的子数列就是一个和为k的整数倍的数列。时间复杂度是O(n)，为了节省搜索的时间，用了C++STL中的哈希表实现unordered_map（在c++11前是hash_map，c++11推荐使用unordered_map）这样空间复杂度是O(k)，查找的时间复杂度是O(1)。各种省。最后跑了16ms，战胜100%cpp提交答案……
class Solution {public:bool checkSubarraySum(vector<int>& nums, int k){ if (nums.size() < 2) return false; int runningSum = 0; unordered_map<int, int> quickFind; quickFind[0] = -1; for(int i = 0; i < nums.size(); i++) { runningSum += nums[i]; if(k != 0) runningSum %= k; std::unordered_map<int, int>::iterator it; it = quickFind.find(runningSum); if(it == quickFind.end()) quickFind[runningSum] = i; else if(i - it->second > 1) return true; } return false;}};要注意的是，hash_map的实现其实是分三部分，包括一个vector，一个list和一个pair，其中vector用于保存桶，list用于进行冲突处理，pair用于保存key->value结构。哈希表的一个重要问题就是如何解决映射冲突的问题。不知道unordered_map的实现是不是也类似，不过原理肯定也是差不多的，一个数据结构保存桶，一个数据结构处理冲突，一个数据结构来保存。
另外要熟习unordered_map的用法，其实和map用法差不多，他们的insert都是要insert一个pair的，这需要我们做一个std::make_pair，这样代码上看上去很复杂，其实在插入的时候，直接可以当数组用。即map[ke]=value。更加方便
还有用unordered_set的，其实效果一样。
新闻热点
疑难解答
