非负数组中找到和为K的倍数的连续子数组
详见：https://leetcode.com/problems/continuous-subarray-sum/description/
Java实现：
方法一：
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
for(int i=0;i<nums.length;++i){
int sum=nums[i];
for(int j=i+1;j<nums.length;++j){
sum+=nums[j];
if(sum==k){
return true;
}
if(k!=0&&sum%k==0){
return true;
}
}
}
return false;
}
}
方法二：
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
if(nums==null){
return false;
}
HashSet<Integer> sums=new HashSet<>();
int sum=0;
for(int i=0;i<nums.length;++i){
sum+=nums[i];
if((k!=0&&sums.contains(sum%k))||(i!=0&&sum==k)){
return true;
}else if(k!=0){
sums.add(sum%k);
}
}
return false;
}
}
方法三：用HashMap保存sum对k取余数，如果前序有余数也为sum%k的位置，那么就存在连续子数组和为k的倍数。
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
Map<Integer,Integer> map=new HashMap<Integer,Integer>(){{put(0,-1);}};
int sum=0;
for(int i=0;i<nums.length;++i){
sum+=nums[i];
if(k!=0){
sum%=k;
}
Integer prev=map.get(sum);
if(prev!=null){
if(i-prev>1){
return true;
}
}else{
map.put(sum,i);
}
}
return false;
}
}
C++：
方法一：
class Solution {
public:
bool checkSubarraySum(vector<int>& 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<int>& nums, int k)
{
int n = nums.size(), sum = 0, pre = 0;
unordered_set<int> 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