Subarray Sum 2

TAG : subarray + binary_search

[1, 2, 3, 4] [1, 3]

给出一个所有数为正数的数组，还有一个区间，找出在这个区间内可能的子数组的个数

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

提示：

prefixsum数组肯定是递增的。对于当前的prefix[j], 使用二分法找出

sum[i][j] = prefix[j] - prefix[i-1];

对于prefix[1]来说，当前的prefix数组是[0, 1]

left < prefix[j] - prefix[i-1] < right

prefix[i-1] < 3-1 = 2

prefix[i-1] > 3-3 = 0

0 < prefix[i-1] < 2

prefix数组为[0, 1] 所以是全部 2个

code

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 ret = 0;
        int n = A.size();
        if(n == 0)
        {
            return 0;
        }

        vector<int> prefix;
        prefix.push_back(0);
        int sum = 0;
        for(int i = 1; i <= n; i++)
        {
            sum += A[i-1];

            int left = sum - end;
            int right = sum - start;
            int range = binarysearch(prefix, left, right);
            //cout<<sum<<" "<<left<<" "<<right<<" "<<range<<endl;
            ret += range;

            prefix.push_back(sum);
        }
        return ret;
    }

    int binarysearch(vector<int>& A, int left, int right)
    {
        // find the first element >= left;
        // find the last element <= right;

        if(left > right || A.front() > right || A.back() < left)
        {
            return 0;
        }

        int left_index = 0;
        int right_index = A.size()-1;

        int s = 0;
        int e = A.size()-1;


        while(s + 1 < e)
        {
            int mid = (s+e)/2;
            if(A[mid] >= left)
            {
                e = mid;
            }
            else
            {
                s = mid;
            }
        }

        if(A[e] >= left)
        {
            left_index = e;
        }
        if(A[s] >= left)
        {
            left_index = s;
        }

        // right index

        s = 0;
        e = A.size()-1;

        while(s + 1 < e)
        {
            int mid = (s+e)/2;
            if(A[mid] <= right)
            {
                s = mid;
            }
            else
            {
                e = mid;
            }
        }

        if(A[s] <= right)
        {
            right_index = s;
        }
        if(A[e] <= right)
        {
            right_index = e;
        }

        return right_index-left_index+1;

    }


};