How do I handle large arrays without generating all subarray sums?

Use prefix sums and binary search over possible sum values to count subarrays within the target range instead of full sorting.

Why is binary search over sum space preferred here?

It allows efficiently locating the subarray sums that correspond to the left and right indices without generating the entire sorted array.

Do I need to sort the subarray sums explicitly?

No, counting sums via prefix sums in binary search eliminates the need for full sorting, saving time and space.

How should I apply modulo 10^9 + 7 in this problem?

Accumulate the sum incrementally while applying modulo 10^9 + 7 to avoid integer overflow.

What pattern does this problem follow?

It follows the 'Binary search over the valid answer space' pattern combined with prefix sums for efficient subarray sum counting.

#1508

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

子数组和排序后的区间和

给你一个数组 nums ，它包含 n 个正整数。你需要计算所有非空连续子数组的和，并将它们按升序排序，得到一个新的包含 n * (n + 1) / 2 个数字的数组。请你返回在新数组中下标为 left 到 right （下标从 1 开始）的所有数字和（包括左右端点）。由于答案可能很大，请你将它对…

数组双指针二分查找排序前缀和

题目描述

给你一个数组 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^3
nums.length == n
1 <= nums[i] <= 100
1 <= left <= right <= n * (n + 1) / 2

lightbulb

解题思路

方法一：模拟

我们可以按照题目的要求，生成数组 $\textit{arr}$ ，然后对数组进行排序，最后求出 $[\textit{left}-1, \textit{right}-1]$ 范围的所有元素的和，得到结果。

时间复杂度 $O(n^2 \times \log n)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 为题目给定的数组长度。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        arr = []
        for i in range(n):
            s = 0
            for j in range(i, n):
                s += nums[j]
                arr.append(s)
        arr.sort()
        mod = 10**9 + 7
        return sum(arr[left - 1 : right]) % mod

speed

复杂度分析

指标	值
时间	complexity is O(n log sum) because each binary search step counts subarray sums in O(n) and the range of sums is at most sum(nums). Space complexity is O(1) aside from storing prefix sums.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Expect a solution that avoids generating all subarray sums explicitly.
question_mark
Look for prefix sum optimization before binary search.
question_mark
Check if the candidate correctly counts sums within the desired range.

warning

常见陷阱

外企场景

error
Trying to sort all subarray sums directly leads to TLE for n = 1000.
error
Incorrectly calculating indices in 1-based versus 0-based arrays.
error
Overflowing sum if modulo 10^9 + 7 is not applied incrementally.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute only the k-th smallest subarray sum using the same binary search pattern.
arrow_right_alt
Return multiple disjoint ranges of sorted subarray sums efficiently.
arrow_right_alt
Adapt the solution to allow negative numbers with modified counting in binary search.

help

常见问题

外企场景

继续练习

#2234 花园的最大总美丽值 #1498 满足条件的子序列数目 #1346 检查整数及其两倍数是否存在