# leetcode523. Continuous Subarray Sum

## 题目要求

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 a multiple of k, that is, sums up to n*k where n is also an integer.

Example 1:

Input: [23, 2, 4, 6, 7], k=6 Output: True Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

Example 2:

Input: [23, 2, 6, 4, 7], k=6 Output: True Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.

Note:

1. The length of the array won't exceed 10,000.
2. You may assume the sum of all the numbers is in the range of a signed 32-bit integer.

## 思路一：暴力循环

```    public boolean checkSubarraySum(int[] nums, int k) {
if (nums == null || nums.length <= 1) {
return false;
}
int[] sum = new int[nums.length+1];
sum[0] = 0;
for (int i = 1 ; i<sum.length ; i++) {
sum[i] += sum[i-1] + nums[i-1];
}
for (int i = nums.length ; i>=2 ; i--) {
for (int j = 0 ; j+i<sum.length ; j++) {
int diff = sum[j+i] - sum[j];
if (diff == k || (k!=0 && diff % k == 0)) {
return true;
}
}
}
return false;
}```

## 思路二：记录中间结果

```public boolean checkSubarraySum2(int nums[], int k){

Map<Integer,Integer> map = new HashMap<>();
map.put(0,-1);
int sumSoFar = 0;
for(int i=0; i < nums.length; i++){
sumSoFar = sumSoFar + nums[i];
if(k != 0) sumSoFar = sumSoFar % k;
if(map.containsKey(sumSoFar)){
int start = map.get(sumSoFar);
if(i-start > 1) return true;
}else{
map.put(sumSoFar, i);
}
}
return false;
}```

## 思路三：分治法

```public boolean checkSubarraySum(int[] nums, int lo, int hi, int k){
if(lo==hi) return false;
int mid = lo+(hi-lo)/2;
if(checkSubarraySum(nums, lo, mid, k)) return true;
if(checkSubarraySum(nums, mid+1, hi, k)) return true;
int left = mid, right = mid+1;
int sum = nums[left];
while(left>=lo&&right<=hi){
sum += nums[right];
if((k>0&&sum%k==0)||(k==0&&sum==0)) return true;
--left;
++right;
if(left>=lo){
sum += nums[left];
if((k>0&&sum%k==0)||(k==0&&sum==0))  return true;
}
}
return false;
}
public boolean checkSubarraySum(int[] nums, int k) {
k = Math.abs(k);
return checkSubarraySum(nums, 0, nums.length-1, k);
}```

0 条评论

• ### leetcode368. Largest Divisible Subset

假设有一组值唯一的正整数数组，找到元素最多的一个子数组，这个子数组中的任选两个元素都可以构成Si % Sj = 0 或 Sj % Si = 0。

• ### leetcode363. Max Sum of Rectangle No Larger Than K

现有一个由整数构成的矩阵，问从中找到一个子矩阵，要求该子矩阵中各个元素的和为不超过k的最大值，问子矩阵中元素的和为多少? 注：后面的文章中将使用[左上角顶点坐标...

• ### leetcode410. Split Array Largest Sum

将一个长度为n的正整数数组分割为m个非空的连续子数组，并分别计算每个子数组中所有元素的和。求一种分割方式，使得该分割方式生成的最大子数组和为所有分割方式中最小的...

• ### LeetCode. 209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0...

• ### 分割等和子集

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

• ### 面试中可能被问到的常用排序算法

排序算法是一种比较简单的算法，从我们一开始接触计算机编程开始接触的可能就是排序或者搜索一类的算法，但是因为排序在其他的一些算法中应用较多，所以为了提高性能已经研...

• ### 只出现一次的元素

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

• ### LeetCode算法题(一)

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。

• ### [LeetCode] 938. Range Sum of BST 二叉搜索树的区间和

Given the root node of a binary search tree, return the sum of values of all nod...