Massive Algorithms: LeetCode 523 - Continuous Subarray Sum + Lintcode 402, 403: Continuous Subarray Sum I,II

LeetCode 523 - Continuous Subarray Sum + Lintcode 402, 403: Continuous Subarray Sum I,II

https://leetcode.com/problems/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 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/
这道题目如果很直观地做，很容易就想到暴力的方法，利用二重循环遍历上界和下界，然后再用一个循环将这一段区间内的元素加起来，时间复杂度为

O (n^{3})

。稍微进行一点优化，利用

s u m (i, j) = s u m (j) - s u m (i - 1)

就可以得到一个时间复杂度为

O (n^{2})

的算法

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].

https://algorithm.yuanbin.me/zh-hans/problem_misc/continuous_subarray_sum.html

由于需要返回区间索引值，那么显然需要额外变量记录区间起止处。若使用题解2中提到的sum - minSum的区间和更新方式，索引终止处容易得知是sum - minSum > maxSub时的i, 问题是索引起始处如何确定。容易得知索引起始处如果更新，必然在minSum > sum时，但问题在于满足此条件的可能不止一处，所以我们需要先记录这个索引值并在sum - minSum > maxSub时判定索引终止值是否大于索引起始值，不小于则更新。

此题难以一次 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;
    }

http://www.jiuzhang.com/solutions/continuous-subarray-sum/

    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 II
https://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;
    }

LeetCode 523 - Continuous Subarray Sum + Lintcode 402, 403: Continuous Subarray Sum I,II

Example

Labels

Popular Posts