Massive Algorithms: LintCode 138, 404

LintCode 138, 404 - Subarray Sum I,II

http://www.cnblogs.com/easonliu/p/4543647.html

Subarray Sum

Given an integer array, find a subarray where the sum of numbers is zero. Your code should return the index of the first number and the index of the last number.

Example

Given [-3, 1, 2, -3, 4], return [0, 2] or [1, 3].

用hashmap来存从nums[0]到nums[i]的和以及当前下标i，遍历数组求前缀和acc[i]，如果发现acc[i]的值已经在hashmap中的，那么说明已经找到一段子数组和为0了。

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

    public ArrayList<Integer> subarraySum(int[] nums) {
        // write your code here
       
        int len = nums.length;
       
        ArrayList<Integer> ans = new ArrayList<Integer>();
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
       
        map.put(0, -1);//\\
       
        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum += nums[i];
           
            if (map.containsKey(sum)) {
                ans.add(map.get(sum) + 1);
                ans.add(i);
                return ans;
            }
            
            map.put(sum, i);
        }
       
        return ans;
    }

https://zhengyang2015.gitbooks.io/lintcode/subarray_sum_ii_404.html

Given an integer array, find a subarray where the sum of numbers is in a given interval. Your code should return the number of possible answers. (The element in the array should be positive)

Example

Given [1,2,3,4] and interval = [1,3], return 4. The possible answers are:

[0, 0] [0, 1] [1, 1] [2, 2]

方法1: 和I一样，用prefix来解。首先计算prefix，然后根据prefix来计算每一段subarray的sum。右边prefix－左边prefix等于中间这一段subarray的sum。左边prefix从0枚举到n－1，右边prefix从当前左边往右一位开始枚举到n，这样可以得到所有sunarray的sum，每一个sum如果在interval之内则count增加1个。O(n^2)。

方法2: 和1思想其实一样，每次右边界j向右移动一位，然后枚举左边界从0到j－1，计算左右边界array的sum，看这些sum是否在interval中。

    public int subarraySumII(int[] A, int start, int end) {
        // Write your code here
        if(A == null || A.length == 0 || start > end){
            return 0;
        }
        //preix version
        int[] sum = new int[A.length + 1];
        sum[0] = 0;
        for(int i = 1; i <= A.length; i++){
            sum[i] = sum[i - 1] + A[i - 1];
        }

        int count = 0;
        for(int i = 0; i < A.length; i++){
            for(int j = i + 1; j <= A.length; j++){
                int diff = sum[j] - sum[i];
                if(diff >= start && diff <= end){
                    count++;
                }
            }
        }

        return count;
    }

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

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 their are duplicate answer, return anyone)

Example

Give [-3, 1, 3, -3, 4], return [1,4].

和题 Maximum Subarray 几乎一模一样，只是返回值要求不一样。由于需要返回区间索引值，那么显然需要额外变量记录区间起止处。若使用题解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;
    }

先求出前缀和，然后枚举求两个前缀和的差。如果差在start与end之间，就给res+1。注意前缀和数组前要插入一个0。

http://blog.hyoung.me/cn/2017/02/subarray-sum-ii/
这题（LintCode 404）应该算是滑动窗口类问题的巅峰之作了，但究其本质，与寻常的滑动窗口类题目并无二致。同时，与 Subarray 系列题目一样，我们也可以使用基于前缀和的二分搜索来解决。

因为这里我们的搜索目标是一个区间，所以可以等效于同时维护两个滑动窗口，一个窗口代表目标区间的最小值，另一个则是目标区间的最大值。因此，相较于常规使用一个指针来维护滑动窗口的尾部，，我们需要使用两个指针分别来维护这两个滑动窗口。但是需要注意的时，这两个尾部指针并不完全独立，比如指向目标区间最大值的指针肯定不会处于指向目标区间最小值的指针之前。

思路明确后，其实实现起来与只有一个指针的情况大同小异


int subarraySumII(vector<int>& A, int start, int end) {

    int n = A.size();

    if (n == 0)

        return 0;

    

    int counts = 0;

    

    int head = 0;

    int lowTail = 0, highTail = 0;

    int lowSum = 0, highSum = 0;

    

    while (head < n) {

        // find lower bound for window end (included)

        while (lowTail < n && lowSum + A[lowTail] < start) {

            lowSum += A[lowTail++];

        }

        

        // find upper bound for window end (excluded)

        if (highTail < lowTail) {

            highTail = lowTail;

            highSum = lowSum;

        }

        

        while (highTail < n && highSum + A[highTail] <= end) {

            highSum += A[highTail++];

        }

        

        // add numbers of valid subarray that starts at A[head]

        counts += (highTail - lowTail);

        

        // throw A[head]

        lowSum -= A[head];

        highSum -= A[head];

        head++;

    }

    

    return counts;

}

这里我们采用[lowTail, highTail)来标注符合要求的滑动窗口尾部区间，即[head, lowTail]是第一个以head开头并符合要求的子数组，而[head, highTail-1]是最后一个以head开头并符合要求的子数组。

这里虽然有嵌套的循环，但从整体来看，三个指针分别扫过一遍数组，所以时间复杂度为

O (N)

。

前缀和数组二分搜索解法

非负整数 Subarray 相关题目的一个常用解法就是通过计算前缀和数组，然后利用二分搜索来找到目标。在这里，类似的思路同样适用。举个例子，假设给定一个目标区间[low, high]，当我们遍历到prefixSum[i]时，我们的搜索范围为prefixSum[0,i-1]，而搜索目标有两个：

$a r g m i n_{j} (prefixSum [i] - prefixSum [j] \leq high)$
$\Rightarrow a r g m i n_{j} (prefixSum [i] - high \leq prefixSum [j])$
$a r g m a x_{k} (prefixSum [i] - prefixSum [k] \geq low)$
$\Rightarrow a r g m a x_{k} (prefixSum [i] - low \geq prefixSum [k])$

分别为第一个大于或等于prefixSum[i] - high的位置，即最左边的位置，以及最后一个小于或等于prefixSum[i] - low的位置，即最右边的位置。

看上去这是两种二分搜索，但这里有个小技巧，那就是把后一个条件稍稍修改，变成第一个大于或等于prefixSum[i] - low + 1的位置，等效于我们把需要找的位置往后移了一位。


int subarraySumII(vector<int>& A, int start, int end) {

    int n = A.size();

    if (n == 0)

        return 0;

    

    vector<int> prefixSum(n + 1, 0);

    for (int i = 1; i <= n; ++i) {

        prefixSum[i] = prefixSum[i - 1] + A[i - 1];

    }

    

    int counts = 0;

    for (int i = 1; i <= n; ++i) {

        int lowBound = find(prefixSum, i, prefixSum[i] - end);

        int highBound = find(prefixSum, i, prefixSum[i] - start + 1);

        counts += (highBound - lowBound);

    }

    

    return counts;

}



// find the first pos in nums such that nums[pos] >= target

int find(vector<int>& nums, int len, int target) {

    if (target > nums[len - 1])

        return len;

        

    int lo = 0, hi = len - 1;

    int firstShow = 0;

    while (lo <= hi) {

        int mid = lo + (hi - lo) / 2;

        if (nums[mid] >= target) {

            firstShow = mid;

            hi = mid - 1;

        } else {

            lo = mid + 1;

        }

    }

    

    return firstShow;

}

相较于上面一种解法，我们固定的是滑动窗口头部，在这里我们其实固定的是滑动窗口尾部，然后去找符合要求的头部区间。

这里的特殊情况值得详细分析一下。首先是要明确对于找highBound而言，我们本质上是需要找到满足限制条件的滑动窗口头部的最后一个位置，而在这里我们是间接地去达到这个要求，即找到该位置的下一位。当target已经大于搜索区间的最后一个元素后，我们直接返回len即可，因为此时滑动窗口头部的最后一个位置已经是len-1，不能再往后移动了。对于找其他情况而言，逻辑就更简单一点，初始化为0即可。

LintCode 138, 404 - Subarray Sum I,II

Subarray Sum

Example

Labels

Popular Posts