Subarray Sum II

Given an integer array, find a subarray where the sum of numbers is between two given interval. Your code should return the number of possible answer.

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

http://www.lintcode.com/en/problem/subarray-sum-ii/

Discussion

比较难。跟Subarray Sum问题一样，也要用到accumulated sum，对于sum[i]，不再判断其是否出现过，而是判断满足$$start <= A[i]-X <= end$$的$$X$$有多少个。也就是在累计和中查找满足$$A[i]-end <= X <= A[i]-start$$的个数。为了方便查找，先排序，再用二分查找。

比如上面例子，累计和为[1,3,6,10]。对6而言，是不满足[1,3]的，这时候对结果就没有贡献了吗？不是的，如果累计和里面有[1,5]的数，说明是存在相应的subarray满足条件的。

这个题同时也考了二分查找，只是不再返回target的index，而是返回小于等于target的元素的个数，这是要修改的地方。另外累计和也可以用输入vector保存，节省空间。

Solution

class Solution {
public:
    /**
     * @param A an integer array
     * @param start an integer
     * @param end an integer
     * @return the number of possible answer
     */
    int subarraySumII(vector<int>& A, int start, int end) {
        // Write your code here
        int n = A.size();
        for(int i=1; i<n; i++) {
            A[i] += A[i-1];
        }
        int result = 0;
        sort(A.begin(), A.end());
        for(int i=0; i<n; i++) {
            if(A[i] <= end && A[i] >= start) {//A[i]要记得判断。
                result++;
            }
            int larger = A[i] - start;
            int smaller = A[i] - end;
            result += (find(A, larger) - find(A, smaller-1));
        }
        return result;
    }
private:
    int find(vector<int> A, int val) {//返回A中小于等于val的元素的个数
        int start = 0, end = A.size()-1;
        int cnt = 0;
        int mid;
        while (start+1 <end) {//二分法经典四步
            mid = start+(end-start)/2;
            if(A[mid] == val) {
                start = mid;//虽然end=mid也通过了，但我觉得应该是start=mid，我们是为了找到尽可能多的满足条件的元素数，而不是第一次出现的地方。所以判断结果的时候也是先判断end。
            } if(A[mid] > val) {
                end = mid;
            } else {
                start = mid;
            }
        }
        if(val >= A[end]) {
            return end+1;//加1是因为返回个数不是index
        }
        if(val >= A[start]) {
            return start+1;
        }
        return 0;
    }
};

$$start <= A[i]-X <= end$$条件换成$$start <= X-A[i] <= end$$也是一样的，相应的coding部分变成int larger = A[i] +end; int smaller = A[i] +start;