非负数组中找到和为K的倍数的连续子数组

详见：https://leetcode.com/problems/continuous-subarray-sum/description/

Java实现：

方法一：

class Solution {    public boolean checkSubarraySum(int[] nums, int k) {        for(int i=0;i

方法二：

class Solution {    public boolean checkSubarraySum(int[] nums, int k) {        if(nums==null){           return false;        }        HashSet
     
       sums=new HashSet<>();        int sum=0;        for(int i=0;i
     

方法三：用HashMap保存sum对k取余数，如果前序有余数也为sum%k的位置，那么就存在连续子数组和为k的倍数。

class Solution {    public boolean checkSubarraySum(int[] nums, int k) {        Map
     
       map=new HashMap
      
       (){
    {put(0,-1);}};        int sum=0;        for(int i=0;i
       
        1){                    return true;                }            }else{                map.put(sum,i);            }        }        return false;    }}
       
      
     

C++：

方法一：

class Solution {public:    bool checkSubarraySum(vector
     
      & nums, int k)    {        for (int i = 0; i < nums.size(); ++i)         {            int sum = nums[i];            for (int j = i + 1; j < nums.size(); ++j)            {                sum += nums[j];                if (sum == k)                 {                    return true;                }                if (k != 0 && sum % k == 0)                 {                    return true;                }            }        }        return false;    }};
     

 方法二：

class Solution {public:    bool checkSubarraySum(vector
     
      & nums, int k)    {        int n = nums.size(), sum = 0, pre = 0;        unordered_set
      
        st;        for (int i = 0; i < n; ++i)        {            sum += nums[i];            int t = (k == 0) ? sum : (sum % k);            if (st.count(t))            {                return true;            }            st.insert(pre);            pre = t;        }        return false;    }};
      
     

 参考：http://www.cnblogs.com/grandyang/p/6504158.html