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.執行結果