LeetCode 0327 - Count of Range Sum

Reck Zhang

发布于 2021-08-11 11:19:07

2030

发布于 2021-08-11 11:19:07

文章被收录于专栏：Reck Zhang

Count of Range Sum

Desicription

Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive. Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.

Note:

A naive algorithm of O(n2) is trivial. You MUST do better than that.

Example:

Input: nums = [-2,5,-1], lower = -2, upper = 2,
Output: 3 
Explanation: The three ranges are : [0,0], [2,2], [0,2] and their respective sums are: -2, -1, 2.

Solution

class Solution {
public:
    int countRangeSum(std::vector<int>& nums, int lower, int upper) {
        auto sums = std::multiset<long long>();
        int res = 0;
        sums.insert(0);
        long long sum = 0;
        for(auto num : nums) {
            sum += num;
            res += std::distance(sums.lower_bound(sum - upper), sums.upper_bound(sum - lower));
            sums.insert(sum);
        }
        return res;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019-05-23，如有侵权请联系 cloudcommunity@tencent.com 删除

algorithm