当前位置：首页 > news >正文

算法设计与分析（十三）

news 2026/6/13 13:20:04

Count of Range Sum

更多技术博客 http://vilins.top/

题目

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.

分析

题目的意思是给出一个数组和一个上界和下界，要求在连续的区间范围求和，使得和在给出的下界和上界的范围内，要求给出满足条件的区间的个数。
首先分析这个问题，这里涉及到区间求和，对于这类题目，一般的套路是算一个O(n)复杂度的连续求和，自然，题目也说到，通过一般的方法可以在O(n*n)的复杂度求出来，但这样显然会超时。
这里我们采用分治算法来算，首先我们理解以下基本事实：
对于两个有序的数组，我们假设其为n1和n2，那么对于n1的一个数，如果我们在n2找到最后下标i1使得n2[i1]<n1[i]并且有最后下标i2使得n2[i2]>n1[i]，那么在n2中比n1[i]大的个数为i2-i1。

这里我们采用分治算法用到上述思想，我们不断将整个数组划分成小的问题，在最后一个只有两个元素时开始返回，计算对左边数组的每一个元素，我们利用上述的思想，每处理完一个子问题的时候对其进行归并排序的合并，使得问题的左右两边总是有序的，这样一来不断往上返回，最后得到结果。注意一个问题就是左右两边总是有序的，并且我们注意到左边数组的下标总是小于右边数组的下标，那么得到的范围也必定是从小下标到大的下标。

源码

class Solution { public: void mergeSort(vector<long>& sum, int b, int m, int e) { int n1 = m - b ; int n2 = e - m ; vector<long> left(n1, 0); vector<long> right(n2, 0); for(int i = 0; i < n1; i++) { left[i] = sum[b + i]; } for(int i = 0; i < n2; i++) { right[i] = sum[m + i]; } int i = 0, j= 0; for(int k = b; k < e; k++) { if((left[i] > right[j])) { sum[k] = right[j]; j++; if(j == n2) { for(int q = i; q < n1; q++) { sum[k+1+q-i] = left[q]; } break; } } else { //cout << "k "<< k << endl; sum[k] = left[i]; i++; if(i == n1) { for(int q = j; q < n2; q++) { sum[k+1+q-j] = right[q]; } break; } } } } int merge(vector<long>& sum, int lower, int upper, int low_index, int high_index) { if(high_index - low_index <= 1) { return 0; } int mid = (low_index + high_index)/2; int m = mid, n = mid, count = 0; count = merge(sum, lower, upper, low_index, mid) + merge(sum, lower, upper, mid, high_index); for(int i = low_index; i < mid; i++) { while((sum[m] - sum[i] < lower)&&m < high_index) { m++; } while((sum[n] - sum[i] <= upper)&&n < high_index) { n++; } count += (n - m); } mergeSort(sum, low_index, mid, high_index); //inplace_merge(sum.begin()+low_index, sum.begin()+mid, sum.begin()+high_index); return count; } int countRangeSum(vector<int>& nums, int lower, int upper) { vector<long> sum(nums.size()+1, 0); for(int i = 0; i < nums.size(); i++) { sum[i+1] = sum[i] + nums[i]; } return merge(sum, lower, upper, 0, nums.size()+1); } };