https://leetcode.com/problems/continuous-subarray-sum
https://leetcode.com/problems/continuous-subarray-sum/discuss/99499/Java-O(n)-time-O(k)-space
I did not expect to see k being zero or negative or that a factor would be times zero
https://leetcode.com/problems/continuous-subarray-sum/discuss/173165/Java-solution-beats-100
https://leetcode.com/problems/continuous-subarray-sum/discuss/99503/Need-to-pay-attention-to-a-lot-of-corner-cases...
这道题目如果很直观地做,很容易就想到暴力的方法,利用二重循环遍历上界和下界,然后再用一个循环将这一段区间内的元素加起来,时间复杂度为 。稍微进行一点优化,利用 就可以得到一个时间复杂度为 的算法
Lintcode: (402) Continuous Subarray Sum
https://www.lintcode.com/en/problem/continuous-subarray-sum/
Given an integer array, find a continuous subarray where the sum of numbers is the biggest. Your code should return the index of the first number and the index of the last number. (If there are duplicate answer, return anyone)
http://www.jiuzhang.com/solutions/continuous-subarray-sum/
https://algorithm.yuanbin.me/zh-hans/problem_misc/continuous_subarray_sum_ii.html
https://lefttree.gitbooks.io/leetcode/highFreq/continuousSubarraySum2.html
方法1
https://liut2.gitbooks.io/crazystuff/content/lintcode_403_continuous_subarray_sum_ii.html
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/523_Continuous_Subarray_Sum.java
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.
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:
- The length of the array won't exceed 10,000.
- You may assume the sum of all the numbers is in the range of a signed 32-bit integer.
https://leetcode.com/problems/continuous-subarray-sum/discuss/99499/Java-O(n)-time-O(k)-space
I did not expect to see k being zero or negative or that a factor would be times zero
We iterate through the input array exactly once, keeping track of the running sum mod k of the elements in the process. If we find that a running sum value at index j has been previously seen before in some earlier index i in the array, then we know that the sub-array (i,j] contains a desired sum.
public boolean checkSubarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>(){{put(0,-1);}};;
int runningSum = 0;
for (int i=0;i<nums.length;i++) {
runningSum += nums[i];
if (k != 0) runningSum %= k;
Integer prev = map.get(runningSum);
if (prev != null) {
if (i - prev > 1) return true;
}
else map.put(runningSum, i);
}
return false;
}
https://discuss.leetcode.com/topic/80820/not-smart-solution-but-easy-to-understand public boolean checkSubarraySum(int[] nums, int k) {
if (nums == null || nums.length == 0) return false;
int[] preSum = new int[nums.length+1];
for (int i = 1; i <= nums.length; i++) {
preSum[i] = preSum[i-1] + nums[i-1];
}
for (int i = 0; i < nums.length; i++) {
for (int j = i+2; j <= nums.length; j++) {
if (k == 0) {
if (preSum[j] - preSum[i] == 0) {
return true;
}
} else if ((preSum[j] - preSum[i]) % k == 0) {
return true;
}
}
}
return false;
}
X.https://leetcode.com/problems/continuous-subarray-sum/discuss/173165/Java-solution-beats-100
Thanks for @yz5548 who gave a test case which points out that when we consider the Pigeonhole Principle, we should not forget the length of the answer array should be at least 2. Under such circumstances, the length of input array should satisfy
nums.length + 1 > k * 2
to make sure the distance between two same prefix remainders is larger than one.### Corner cases
1. Element maybe zero
2. Input could be empty
3. K maybe zero or negative
### Solution
1. We store the prefix sum mod k rather than prefix sum. When two prefix sums with the same remainder appear, we got our answer.
Furthermore, if `nums.length + 1 > k * 2` the answer is definitely true.
public boolean checkSubarraySum(int[] nums, int k) {
k = k == 0 ? Integer.MAX_VALUE : (k < 0 ? -k : k); // make sure k is positive; if k is zero, we won't do mod at all
if ((nums.length + 2) / 2 > k) return true; // we have (length + 1 > k * 2) prefix sum but k remainder and k positions that the same remainders next to each other, then there is at least two prefix with the same remainder and the distance is larger than one
Set<Integer> set = new HashSet<>();
int last = 0; // the prefix sum one element earlier
for (int num : nums) {
int cur = (last + num) % k; // get newest prefix sum mod k
if (set.contains(cur)) return true;
set.add(last); // add old prefix sum into HashSet
last = cur; // update old prefix sum
}
return false;
}
https://leetcode.com/problems/continuous-subarray-sum/discuss/99503/Need-to-pay-attention-to-a-lot-of-corner-cases...
This problem contributed a lot of bugs to my contest score... Let's read the description again, pay attention to
red
sections:
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
.
Some
damn it!
test cases:- [0], 0 -> false;
- [5, 2, 4], 5 -> false;
- [0, 0], 100 -> true;
- [1,5], -6 -> true;
etc...
why do we need to do sumToIndex.put(0, -1) ?
public boolean checkSubarraySum(int[] nums, int k) {
// Since the size of subarray is at least 2.
if (nums.length <= 1) return false;
// Two continuous "0" will form a subarray which has sum = 0. 0 * k == 0 will always be true.
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] == 0 && nums[i + 1] == 0) return true;
}
// At this point, k can't be "0" any longer.
if (k == 0) return false;
// Let's only check positive k. Because if there is a n makes n * k = sum, it is always true -n * -k = sum.
if (k < 0) k = -k;
Set<Integer> sums = new HashSet<>();
int sum = 0;
sums.add(0);
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (i > 0) {
// Validate from the biggest possible n * k to k
for (int j = (sum / k) * k; j >= k; j -= k) {
if (sums.contains(sum - j)) return true;
}
}
sums.add(sum);
}
return false;
}
http://tianshilei.me/2017/03/25/leetcode523/这道题目如果很直观地做,很容易就想到暴力的方法,利用二重循环遍历上界和下界,然后再用一个循环将这一段区间内的元素加起来,时间复杂度为 。稍微进行一点优化,利用 就可以得到一个时间复杂度为 的算法
Lintcode: (402) Continuous Subarray Sum
https://www.lintcode.com/en/problem/continuous-subarray-sum/
Given an integer array, find a continuous subarray where the sum of numbers is the biggest. Your code should return the index of the first number and the index of the last number. (If there are duplicate answer, return anyone)
Give
[-3, 1, 3, -3, 4]
, return [1,4]
.
此题难以一次 bug-free, 需要小心更新索引值。
public ArrayList<Integer> continuousSubarraySum(int[] A) {
ArrayList<Integer> result = new ArrayList<Integer>();
if (A == null || A.length == 0) return result;
int sum = 0, minSum = 0, maxSub = Integer.MIN_VALUE;
int first = 0, last = 0;
int first2 = 0; // candidate for first
for (int i = 0; i < A.length; i++) {
if (minSum > sum) {
minSum = sum;
first2 = i;
}
sum += A[i];
if (sum - minSum > maxSub) {
maxSub = sum - minSum;
last = i;
// update first if valid
if (first2 <= last) first = first2;
}
}
result.add(first);
result.add(last);
return result;
}
public ArrayList<Integer> continuousSubarraySum(int[] A) { ArrayList<Integer> result = new ArrayList<Integer>(); result.add(0); result.add(0); int len = A.length; int start = 0, end = 0; int sum = 0; int ans = -0x7fffffff; for (int i = 0; i < len; ++i) { if (sum < 0) { sum = A[i]; start = end = i; } else { sum += A[i]; end = i; } if (sum >= ans) { ans = sum; result.set(0, start); result.set(1, end); } } return result; }https://segmentfault.com/a/1190000004390380
- 在res初始化时不放两个0进去,res的长度还是0,在for循环里会出问题。
- 循环里先判断上一次的结果,再执行sum+=A[i],减少不必要的分支语句。
public ArrayList<Integer> continuousSubarraySum(int[] A) {
ArrayList<Integer> res = new ArrayList<Integer>();
if (A == null || A.length == 0) {
return res;
}
int sum = A[0];
int max = sum;
int start = 0, end = 0;
res.add(0);
res.add(0);
for (int i = 0; i < A.length; i++) {
if (sum > max) {
res.set(0, start);
res.set(1, i-1); //here the index comes from last loop, so is (i-1)
max = sum;
}
if (sum < 0) {
start = i;
end = i;
sum = 0;
}
sum += A[i];
}
if (sum > max) {
res.set(0, start);
res.set(1, A.length-1);
}
return res;
}
Lintcode 403: Continuous Subarray Sum IIhttps://algorithm.yuanbin.me/zh-hans/problem_misc/continuous_subarray_sum_ii.html
Given an integer array, find a continuous rotate subarray where the sum of numbers is the biggest. Your code should return the index of the first number and the index of the last number. (If their are duplicate answer, return anyone. The answer can be rorate array or non- rorate array)
Example
Give
[3, 1, -100, -3, 4]
, return [4,1]
.
在上题的基础上容易想到可以将
first
和last
分四种情况讨论,然后再逆向求大于0的最大和即可,但是这种想法忽略了一种情况——旋转后的最大值可能由两段子数组和构成,而这种情况如果用上题的解法则会被忽略。
所以这道题的正确解法不是分
first
和last
四种情况讨论,而是利用旋转数组的特性。第一种情况,无论怎么拼接原数组中的数组和都无法大于最大的单一数组和;第二种情况则相反。所以现在问题的关键则转化为怎么求第二种情况。首先可以明确一点,最终得到的数组和索引必须连续(含首尾相接)。也就是说情况二一旦出现,则我们可以将原数组中挖空一小段,现在问题来了:到底要挖掉多少元素?
我们的目标是使得挖掉后的元素值最大。由于分段求解不容易(被隔开),但是被挖掉的元素索引是挨着的!正难则反!由于数组的总和是一定的,那么我们只要求得被挖掉部分元素的最小值即可得两边子数组的最大值!最后判断两个最大值孰大孰小就可以了。
public ArrayList<Integer> continuousSubarraySumII(int[] A) {
ArrayList<Integer> result = new ArrayList<Integer>();
if (A == null || A.length == 0) return result;
// maximal subarray sum
ArrayList<Integer> sub1 = subSum(A, 1);
// minimal subarray sum
ArrayList<Integer> sub2 = subSum(A, -1);
int first = 0, last = 0;
if (sub1.get(3) - sub2.get(2) > sub1.get(2)) {
last = sub2.get(0) - 1;
first = sub2.get(1) + 1;
} else {
first = sub1.get(0);
last = sub1.get(1);
}
// corner case(all elements are negtive)
if (last == -1 && first == A.length) {
first = sub1.get(0);
last = sub1.get(1);
}
result.add(first);
result.add(last);
return result;
}
private ArrayList<Integer> subSum(int[] A, int sign) {
ArrayList<Integer> result = new ArrayList<Integer>();
// find the max/min subarray sum from [0...A.length]
int sum = 0, minSum = 0, maxSub = Integer.MIN_VALUE;
if (sign == -1) maxSub = Integer.MAX_VALUE;
int first = 0, last = 0;
int first2 = 0; // candidate for first
for (int i = 0; i < A.length; i++) {
if (sign * minSum > sign * sum) {
minSum = sum;
first2 = i;
}
sum += A[i];
if (sign * (sum - minSum) > sign * maxSub) {
maxSub = sum - minSum;
last = i;
// update first if valid
if (first2 <= last) first = first2;
}
}
result.add(first);
result.add(last);
result.add(maxSub);
result.add(sum);
return result;
}
由于既需要求最大子数组和,也需要求最小子数组和,我们将这一部分写成一私有方法,并加入sign
控制符号。如果两段子数组和大于一段子数组和时,新的first
和last
正好相反。且在数组全为负时需要排除,直接使用单一子数组和最大的情况。https://lefttree.gitbooks.io/leetcode/highFreq/continuousSubarraySum2.html
方法1
- 按I的方法求出的结果
- 从整个array中减去中间最小的subarray,需要rotate的array
思路是这样的,像楼上说的两种情况,不rotate的 和rorate的。不rotate的和Continuous Subarray Sum I做法一样,不说了。rotate的,可以这样想,rotate的结果其实相当于是把原来的array中间挖了一段连续的array,那么挖哪一段呢?肯定是和最小的一段连续array。这样解法就出来了。
类似Continuous Subarray Sum I,在I里面是找到连续和最大的一段subarray,在这里,不仅找到和最大的一段连续array,并且也找到和最小的一段连续array,然后用整个array的sum减去这个最小的和,如果大于不rotate的最大和,那么解就是挖去的这段array的(尾+1, 头-1)
有一个edge case就是当array全部为负时,要挖去的array就是整个array,这个要注意一下。
方法2
首尾可以相连的题目可以想到在array的尾部再加上另一个copy,然后用I的方法求结果,但是要注意长度不能超过原有array的长度
https://zhengyang2015.gitbooks.io/lintcode/continuous_subarray_sum_ii_403.html public ArrayList<Integer> continuousSubarraySumII(int[] A) {
// Write your code here
if(A == null || A.length == 0){
return new ArrayList<Integer>();
}
ArrayList<Integer> res = new ArrayList<Integer>();
res.add(0);
res.add(0);
int total = 0;
int start = 0;
int end = 0;
int local = 0;
int global = Integer.MIN_VALUE;
//先找不循环情况下最大子数组
for(int i = 0; i < A.length; i++){
total += A[i];
if(local > 0){
local += A[i];
end = i;
}else{
local = A[i];
start = end = i;
}
if(local > global){
global = local;
res.set(0, start);
res.set(1, end);
}
}
start = 0;
end = -1;
local = 0;
//找最小子数组,数组总和减去最小子数组即为又循环情况下最大子数组
for(int i = 0; i < A.length; i++){
if(local <= 0){
local += A[i];
end = i;
}else{
local = A[i];
start = end = i;
}
//若最小数组为整个数组(即所有元素为负),则返回第一种情况结果
if(start == 0 && end == A.length - 1){
continue;
}
//比较又循环情况和无循环情况大小,取大者
if(total - local > global){
global = total - local;
//为了防止出现最小子数组包含头尾而导致越界
res.set(0, (end + 1) % A.length);
res.set(1, (start - 1 + A.length) % A.length);
}
}
return res;
}
https://liut2.gitbooks.io/crazystuff/content/lintcode_403_continuous_subarray_sum_ii.html
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/523_Continuous_Subarray_Sum.java
public boolean checkSubarraySum(int[] nums, int k) {
k = k == 0 ? Integer.MAX_VALUE : (k < 0 ? -k : k);
if (nums.length > k) return true;
Set<Integer> set = new HashSet<>();
int last = 0;
for (int num : nums) {
int cur = (last + num) % k;
if (set.contains(cur)) return true;
set.add(last);
last = cur;
}
return false;
}
sum - minSum
的区间和更新方式,索引终止处容易得知是sum - minSum > maxSub
时的i
, 问题是索引起始处如何确定。容易得知索引起始处如果更新,必然在minSum > sum
时,但问题在于满足此条件的可能不止一处,所以我们需要先记录这个索引值并在sum - minSum > maxSub
时判定索引终止值是否大于索引起始值,不小于则更新。