美文网首页
Count of Range Sum

Count of Range Sum

作者: 我叫胆小我喜欢小心 | 来源:发表于2017-04-26 11:08 被阅读87次

    题目来源
    给一个数组,求在某个范围内的子串和个数。
    这道题搞了半天,理解了半天,写了半天,感觉自己弱爆了。
    主要在于利用和数组,利用归并排序,分成两堆的时候,前后是有序的,就是说右堆的元素在左堆的元素和索引的后边,所以可以直接两个和相减表示原数组的某个子串和。
    然后归并排序的过程也很巧妙,利用了一个cache来存储排好序的数组。
    左堆和右堆元素比较,因为左右堆都是各自排好序的,所以其实本质上就是双指针向后移动。

    class Solution {
    public:
        int countRangeSum(vector<int>& nums, int lower, int upper) {
            int n = nums.size();
            if (n == 0)
                return 0;
            vector<long long> sums(n+1, 0);
            for (int i=0; i<n; i++)
                sums[i+1] = sums[i] + nums[i];
            return mergeSortWhileCount(sums, 0, n+1, lower, upper);
        }
        
        int mergeSortWhileCount(vector<long long>& sums, int start, int end, int lower, int upper)
        {
            if (end - start <= 1)
                return 0;
            int mid = (start + end) / 2;
            int cnt = mergeSortWhileCount(sums, start, mid, lower, upper)
            + mergeSortWhileCount(sums, mid, end, lower, upper);
            int j = mid, k = mid, t = mid, len = 0;
            vector<long long> cache(end-start, 0);
            for (int i=start, s=0; i<mid; i++, s++) {
                while (j < end && sums[j] - sums[i] < lower) j++;
                while (k < end && sums[k] - sums[i] <= upper) k++;
                while (t < end && sums[t] < sums[i]) cache[s++] = sums[t++];
                cache[s] = sums[i];
                len = s;
                cnt += k - j;
            }
            for (int i=0; i<=len; i++)
                sums[start+i] = cache[i];
            return cnt;
        }
    };
    

    相关文章

      网友评论

          本文标题:Count of Range Sum

          本文链接:https://www.haomeiwen.com/subject/solizttx.html