1.题目基本信息

1.1.题目描述

给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。

区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

1.2.题目地址

https://leetcode.cn/problems/count-of-range-sum/description/

2.解题方法

2.1.解题思路

归并排序。求nums的前缀和数组，并对前缀和数组使用归并排序算法进行排序，在排序过程的归并之前，使用双指针算出rarr[j]-larr[i]在[lower,upper]区间的(i,j)的组合对数，并使用全局变量进行统计总对数，即为题解

3.解题代码

python代码

class Solution:def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:# 思路1：归并排序。求nums的前缀和数组，并对前缀和数组使用归并排序算法进行排序，在排序过程的归并之前，使用双指针算出rarr[j]-larr[i]在[lower,upper]区间的(i,j)的组合对数，并使用全局变量进行统计总对数，即为题解n = len(nums)preSums = [0] * (n + 1)for i in range(n):preSums[i + 1] = preSums[i] + nums[i]self.lower = lowerself.upper = upperself.result = 0self.mergeSort(preSums, 0, n)# print(preSums)# print(self.result)return self.resultdef mergeSort(self, nums:list[int], left:int, right:int):# 第一步，递归将左右两侧进行排序if left >= right:return mid = (right - left) // 2 + leftself.mergeSort(nums, left, mid)self.mergeSort(nums, mid + 1, right)larr = nums[left:mid + 1]rarr = nums[mid + 1:right + 1]# 第二步，找到larr和rarr能够构成的合法情况的对数i, j1, j2 = 0, 0, 0while i < mid + 1 - left:while j1 < right - mid and rarr[j1] < larr[i] + self.lower:j1 += 1while j2 < right - mid and rarr[j2] <= larr[i] + self.upper:j2 += 1self.result += j2 - j1i += 1# 第三步，merge已经排序的部分i, j, k = 0, 0, leftwhile i < mid + 1 - left and j < right - mid:if larr[i] < rarr[j]:nums[k] = larr[i]i += 1k += 1else:nums[k] = rarr[j]j += 1k += 1while i < mid + 1 - left:nums[k] = larr[i]i += 1k += 1while j < right - mid:nums[k] = rarr[j]j += 1k += 1

4.执行结果