class Solution {
public:
int rangeSum(vector<int>& nums, int n, int left, int right) {
}
};
1508. 子数组和排序后的区间和
给你一个数组 nums ，它包含 n 个正整数。你需要计算所有非空连续子数组的和，并将它们按升序排序，得到一个新的包含 n * (n + 1) / 2 个数字的数组。
请你返回在新数组中下标为 left 到 right （下标从 1 开始）的所有数字和（包括左右端点）。由于答案可能很大，请你将它对 10^9 + 7 取模后返回。
示例 1：
输入：nums = [1,2,3,4], n = 4, left = 1, right = 5 输出：13 解释：所有的子数组和为 1, 3, 6, 10, 2, 5, 9, 3, 7, 4 。将它们升序排序后，我们得到新的数组 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10] 。下标从 le = 1 到 ri = 5 的和为 1 + 2 + 3 + 3 + 4 = 13 。
示例 2：
输入：nums = [1,2,3,4], n = 4, left = 3, right = 4 输出：6 解释：给定数组与示例 1 一样，所以新数组为 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10] 。下标从 le = 3 到 ri = 4 的和为 3 + 3 = 6 。
示例 3：
输入：nums = [1,2,3,4], n = 4, left = 1, right = 10 输出：50
提示：
1 <= nums.length <= 10^3nums.length == n1 <= nums[i] <= 1001 <= left <= right <= n * (n + 1) / 2原站题解
cpp 解法, 执行用时: 8 ms, 内存消耗: 8 MB, 提交时间: 2022-12-08 11:38:24
class Solution {
public:
int rangeSum(vector<int>& nums, int n, int left, int right) {
// 求 psums 和 ppsums。
// 注：求 psums 时右挪一个单位；求 ppsums 无需右挪一个单位，它已经随着 psum 右挪
vector<long> psum(n+1, 0), ppsum(n+1, 0);
for(int i = 1; i <= n; ++i)
psum[i] = psum[i-1] + nums[i-1];
for(int i = 1; i <= n; ++i)
ppsum[i] = ppsum[i-1] + psum[i];
// 求 < x 的所有的区间和的和 sum 和个数 cnt
auto get_sum_cnt = [&](int x) -> pair<long ,long> {
long sum = 0, cnt = 0;
for(int i = 0, j = 0; i < n; ++i) {
while(j < n && psum[j+1] - psum[i] < x)
++j;
sum += ppsum[j] - ppsum[i] - (j - i) * psum[i];
cnt += j - i;
}
return {sum, cnt};
};
// 求新数组的第 k 个数（也就是原数组的第 k 小区间和）
auto get_kth = [&](int k) -> long {
int l = 0, r = psum[n];
while(l < r) {
int mid = (l + r + 1) / 2;
auto [sum, cnt] = get_sum_cnt(mid);
if(cnt < k)
l = mid;
else
r = mid - 1;
}
return l;
};
auto f = [&](int k) -> long {
auto x = get_kth(k);
auto [sum, cnt] = get_sum_cnt(x);
return sum + (k - cnt) * x;
};
return (f(right) - f(left - 1)) % (1000000007);
}
};
python3 解法, 执行用时: 84 ms, 内存消耗: 15.2 MB, 提交时间: 2022-12-08 11:37:14
class Solution:
def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
MODULO = 10**9 + 7
prefixSums = [0]
for i in range(n):
prefixSums.append(prefixSums[-1] + nums[i])
prefixPrefixSums = [0]
for i in range(n):
prefixPrefixSums.append(prefixPrefixSums[-1] + prefixSums[i + 1])
def getCount(x: int) -> int:
count = 0
j = 1
for i in range(n):
while j <= n and prefixSums[j] - prefixSums[i] <= x:
j += 1
j -= 1
count += j - i
return count
def getKth(k: int) -> int:
low, high = 0, prefixSums[n]
while low < high:
mid = (low + high) // 2
count = getCount(mid)
if count < k:
low = mid + 1
else:
high = mid
return low
def getSum(k: int) -> int:
num = getKth(k)
total, count = 0, 0
j = 1
for i in range(n):
while j <= n and prefixSums[j] - prefixSums[i] < num:
j += 1
j -= 1
total += prefixPrefixSums[j] - prefixPrefixSums[i] - prefixSums[i] * (j - i)
count += j - i
total += num * (k - count)
return total
return (getSum(right) - getSum(left - 1)) % MODULO
java 解法, 执行用时: 2 ms, 内存消耗: 39.5 MB, 提交时间: 2022-12-08 11:36:44
class Solution {
static final int MODULO = 1000000007;
public int rangeSum(int[] nums, int n, int left, int right) {
int[] prefixSums = new int[n + 1];
prefixSums[0] = 0;
for (int i = 0; i < n; i++) {
prefixSums[i + 1] = prefixSums[i] + nums[i];
}
int[] prefixPrefixSums = new int[n + 1];
prefixPrefixSums[0] = 0;
for (int i = 0; i < n; i++) {
prefixPrefixSums[i + 1] = prefixPrefixSums[i] + prefixSums[i + 1];
}
return (getSum(prefixSums, prefixPrefixSums, n, right) - getSum(prefixSums, prefixPrefixSums, n, left - 1)) % MODULO;
}
public int getSum(int[] prefixSums, int[] prefixPrefixSums, int n, int k) {
int num = getKth(prefixSums, n, k);
int sum = 0;
int count = 0;
for (int i = 0, j = 1; i < n; i++) {
while (j <= n && prefixSums[j] - prefixSums[i] < num) {
j++;
}
j--;
sum = (sum + prefixPrefixSums[j] - prefixPrefixSums[i] - prefixSums[i] * (j - i)) % MODULO;
count += j - i;
}
sum = (sum + num * (k - count)) % MODULO;
return sum;
}
public int getKth(int[] prefixSums, int n, int k) {
int low = 0, high = prefixSums[n];
while (low < high) {
int mid = (high - low) / 2 + low;
int count = getCount(prefixSums, n, mid);
if (count < k) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
public int getCount(int[] prefixSums, int n, int x) {
int count = 0;
for (int i = 0, j = 1; i < n; i++) {
while (j <= n && prefixSums[j] - prefixSums[i] <= x) {
j++;
}
j--;
count += j - i;
}
return count;
}
}
java 解法, 执行用时: 67 ms, 内存消耗: 47.1 MB, 提交时间: 2022-12-08 11:36:25
class Solution {
public int rangeSum(int[] nums, int n, int left, int right) {
final int MODULO = 1000000007;
int sumsLength = n * (n + 1) / 2;
int[] sums = new int[sumsLength];
int index = 0;
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++) {
sum += nums[j];
sums[index++] = sum;
}
}
Arrays.sort(sums);
int ans = 0;
for (int i = left - 1; i < right; i++) {
ans = (ans + sums[i]) % MODULO;
}
return ans;
}
}
python3 解法, 执行用时: 280 ms, 内存消耗: 37.9 MB, 提交时间: 2022-12-08 11:35:39
class Solution:
def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
MODULO = 10**9 + 7
sumsLength = n * (n + 1) // 2
sums = list()
index = 0
for i in range(n):
total = 0
for j in range(i, n):
total += nums[j]
sums.append(total)
sums.sort()
ans = sum(sums[left-1:right]) % MODULO
return ans