题目描述

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.

 

题目大意

求一个数组中不同范围的和满足给定条件的范围的个数，即lower <= nums[i] + nums[i + 1] + ... + nums[j] <= upper

（要求时间复杂度小于O（N²））

 

示例

E1

 

解题思路

基于归并的思想，将数组分为两部分，递归求两部分数组的符合条件的范围个数，再求两个数组之和的满足条件的范围个数。

 

复杂度分析

时间复杂度：O(Nlog（N）)

空间复杂度：O(N)

 

代码

class Solution {public:    int countRangeSum(vector
     
      & nums, int lower, int upper) {        int len = nums.size();        // 需要使用long类型，防止两个数字相加超过int范围        vector
      
        sum(len + 1, 0);        for(int i = 0; i < len; ++i)            sum[i + 1] = (long)(sum[i] + nums[i]);                return solve(sum, lower, upper, 0, len + 1);    }        int solve(vector
       
        & sum, int lower, int upper, int low, int high) {        // 如果数字只包含少于三个数字，则表示不能将数组分为两个部分以及一个中位数        if(high - low <= 1)            return 0;        int mid = (low + high) / 2, m = mid, n = mid, count = 0;        // 递归求取分为两个部分的数组的范围个数        count = solve(sum, lower, upper, low, mid) + solve(sum, lower, upper, mid, high);        // 求两个子数组之间的满足的范围个数        for(int i = low; i < mid; ++i) {            while(m < high && (long)(sum[m] - sum[i]) < (long)lower)                ++m;            while(n < high && (long)(sum[n] - sum[i]) <= (long)upper)                ++n;            count += n - m;        }                inplace_merge(sum.begin() + low, sum.begin() + mid, sum.begin() + high);                return count;    }};