Share my cpp solution based on merge-sort


  • 0
    O
    class Solution {
        vector<long long> x;
        int lo, hi;
    public:
        int countRangeSum(vector<int>& nums, int lower, int upper) {
            x = vector<long long>(nums.size() + 1, 0);
            for (int i = 0; i < nums.size(); i++) x[i + 1] = x[i] + nums[i];
            lo = lower;
            hi = upper;
            int ans = merge_sort(1, nums.size());
            return ans;
        }
        
        int merge_sort(int start, int end) {
            if (start > end) return 0;
            if (start == end) {
                if (x[start] - x[start - 1] >= lo and x[start] - x[start - 1] <= hi) return 1;
                else return 0;
            }
            int mid = start + (end - start) / 2;
            int ans = merge_sort(start, mid) + merge_sort(mid + 1, end);
            ans += merge(start, mid, mid + 1, end);
            return ans;
        }
        
        int merge(int start1, int end1, int start2, int end2) {
            vector<long long> tmp;
            int p = start1, q = start2;
            int ans = 0;
            for (int i = start1; i <= end1; i++) {
                int a = upper_bound(x.begin() + start2, x.begin() + 1 + end2, x[i - 1] + hi) - x.begin(),
                    b = lower_bound(x.begin() + start2, x.begin() + 1 + end2, x[i - 1] + lo) - x.begin();
                ans += a - b;
            }
            while (p <= end1 && q <= end2) {
                if (x[p] < x[q]) tmp.push_back(x[p++]);
                else tmp.push_back(x[q++]);
            }
            while (p <= end1) tmp.push_back(x[p++]);
            while (q <= end2) tmp.push_back(x[q++]);
            for (int i = start1; i <= end2; i++) x[i] = tmp[i - start1];
            return ans;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.