题目描述
思路解析
一句话答案：LeetCode 1508 子数组和排序后的区间和：n≤1000 数据小，直接枚举全部 n×(n+1)/2 个子数组和、升序排序，再取下标 left 到 right 这段求和取模，时间 O(n²log n)、空间 O(n²)。
排序后取第 left 到 right 个，要返回哪个和
给一个全是正整数的数组 nums，先把它所有非空连续子数组各自求和——长度 n 的数组一共有 n×(n+1)/2 个这样的和。把这些和从小到大排成一个新序列，返回新序列里下标 left 到 right（从 1 数起、含两端）这一段的总和，对 10⁹+7 取模。题面 nums=[1,2,3,4]、left=1、right=5 时答案是 13：排序后前 5 个数正好加到 13。
n 最多 1000，把全部子数组和排一遍贵不贵
n 最大只有 1000，子数组和总共 n×(n+1)/2 个，满打满算约 50 万个数。把它们全枚举出来是双重循环、约 O(n²)；对这约 n² 个数排序是 O(n²log n)，大概两千万次比较；再扫一段区间求和。三步里排序最重，合起来 O(n²log n)，这个量级现代机器一秒内跑得完。所以不必绕开枚举去凑更巧的公式，照题意把全部子数组和摆出来、排好、取区间，就够通过。
枚举每个子数组和，真要每段从头加一遍吗
枚举时有个白费力气的地方：固定起点 i，子数组 [i..j] 的和其实就是 [i..j−1] 的和再加上 nums[j] 一个数。要是每延伸一格都从 i 重新累加到 j，同一段前缀会被反复加许多遍。用一个累加变量 s 顶着：起点 i 处 s 归零，内层 j 从 i 往右走，每步 s 加上 nums[j] 就是当前子数组的和，直接记下来。这样每个子数组和只多做一次加法，枚举这步稳定在 O(n²)。
排好序之后，取哪一段、下标怎么减
排好序只是普通升序，真正要小心的是取哪一段。题目的 left、right 从 1 数起，数组下标却从 0 起，要取的是下标 left−1 到 right−1 这一段，忘了减 1 整段区间就整体偏一位，取到的是错的几个数。取出这段后把它们加起来，就是排序前那些子数组和里、第 left 小到第 right 小的总和。
[1,2,3,4] 上 left=1、right=5 算出什么
第一个数当起点：累加变量从 0 起，依次加成 1、3、6、10（对应 [1]、[1,2]、[1,2,3]、[1,2,3,4]）。换第二个数起头，归零后加成 2、5、9；从第三个起得 3、7；从第四个起得 4。收齐 10 个和：1、3、6、10、2、5、9、3、7、4。升序排好是 1、2、3、3、4、5、6、7、9、10，两个 3 各占一格。left=1、right=5 换成下标 0 到 4，取出 1、2、3、3、4，加起来 13，没超过取模上限，答案就是 13。
相等的和别去重，取模也别拖到最后
整套下来时间 O(n²log n)、空间 O(n²)，大头是装下约 n² 个子数组和的那个数组。边界想清三种：子数组只剩单个元素时和就是它自己；left=right 时区间只取排序后那一个数；left=1、right=n×(n+1)/2 时区间盖住全部，答案是所有子数组和之和。还有两处松了就悄悄错：排序时把相等的和去掉一个，长度就少一格、整段跟着错位——本例两个 3 必须都留；取模若拖到最后一次做，区间数一多累计和会先超出整型上限，得边加边对 10⁹+7 取模。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住三步走:枚举出全部子数组和、升序排序、把下标 left 到 right 这一段加起来取模。下面每一帧都在走这三步。
阶段一 · 准备枚举子数组和：上面这排是 nums = [1, 2, 3, 4]。右边面板用来收集所有子数组的和,现在还是空的。我们要枚举的是连续子数组,做法是固定一个起点 i,从 i 往右逐格延伸。一共会得到 4 乘 5 除以 2,也就是 10 个子数组和。
枚举 · 子数组 nums[0..0] = 1：换一个新起点,i = 0。累加变量先归零,加上 nums[0] = 1,得到只含一个元素的子数组 [1],和是 1。把 1 记进面板。
枚举 · 子数组 nums[0..1] = 3：从起点 0 继续往右延伸到下标 1。新进来的数是 nums[1] = 2,直接接到上一段的和 1 上,1 加 2 等于 3。这就是子数组 [1, 2] 的和,记进面板。注意这里复用了上一段的结果,没有从头重算。
枚举 · 子数组 nums[0..2] = 6：从起点 0 继续往右延伸到下标 2。新进来的数是 nums[2] = 3,直接接到上一段的和 3 上,3 加 3 等于 6。这就是子数组 [1, 2, 3] 的和,记进面板。注意这里复用了上一段的结果,没有从头重算。
枚举 · 子数组 nums[0..3] = 10：从起点 0 继续往右延伸到下标 3。新进来的数是 nums[3] = 4,直接接到上一段的和 6 上,6 加 4 等于 10。这就是子数组 [1, 2, 3, 4] 的和,记进面板。注意这里复用了上一段的结果,没有从头重算。
枚举 · 子数组 nums[1..1] = 2：换一个新起点,i = 1。累加变量先归零,加上 nums[1] = 2,得到只含一个元素的子数组 [2],和是 2。把 2 记进面板。
枚举 · 子数组 nums[1..2] = 5：从起点 1 继续往右延伸到下标 2。新进来的数是 nums[2] = 3,直接接到上一段的和 2 上,2 加 3 等于 5。这就是子数组 [2, 3] 的和,记进面板。注意这里复用了上一段的结果,没有从头重算。
枚举 · 子数组 nums[1..3] = 9：从起点 1 继续往右延伸到下标 3。新进来的数是 nums[3] = 4,直接接到上一段的和 5 上,5 加 4 等于 9。这就是子数组 [2, 3, 4] 的和,记进面板。注意这里复用了上一段的结果,没有从头重算。
枚举 · 子数组 nums[2..2] = 3：换一个新起点,i = 2。累加变量先归零,加上 nums[2] = 3,得到只含一个元素的子数组 [3],和是 3。把 3 记进面板。
枚举 · 子数组 nums[2..3] = 7：从起点 2 继续往右延伸到下标 3。新进来的数是 nums[3] = 4,直接接到上一段的和 3 上,3 加 4 等于 7。这就是子数组 [3, 4] 的和,记进面板。注意这里复用了上一段的结果,没有从头重算。
枚举 · 子数组 nums[3..3] = 4：换一个新起点,i = 3。累加变量先归零,加上 nums[3] = 4,得到只含一个元素的子数组 [4],和是 4。把 4 记进面板。
阶段一完成 · 收集到全部子数组和：枚举结束。把面板里的 10 个子数组和按生成顺序铺到舞台上,是 1、3、6、10、2、5、9、3、7、4。从这一帧起,舞台上摆的就是这排子数组和,原来的 nums 退到幕后。下一步要把它们排序。
阶段二 · 升序排序：把这 10 个数从小到大排好。原来的顺序 1、3、6、10、2、5、9、3、7、4,排完变成 1、2、3、3、4、5、6、7、9、10。这一步就是普通的升序排序,语言自带的排序函数即可。排好之后,我们才能按题目要求用下标去取区间。
阶段二 · 重复值都保留：提醒一个容易忽略的点:子数组 [3] 和子数组 [1, 2] 的和都是 3,排序后这两个 3 各自占一格,不会去重。绿色高亮的就是这两个 3,它们落在下标 2 和下标 3。题目要的是带重复的完整序列,千万别当成集合去掉重复。
阶段三 · 圈定区间 [1, 5]：现在做第三步,区间求和。题目的下标从 1 开始,left = 1、right = 5。换算到我们这从 0 开始的数组,就是下标 0 到下标 4,一共 5 个数。底色框住的就是要相加的这一段。这个减 1 的换算很关键,别搞错。
区间求和 · 加入下标 0(值 1)：把下标 0 上的数 1 加进来。之前累计是 0,加上 1 得到 1。绿色部分就是已经累加进去的范围,紫色是这一帧刚加入的格子。继续往右加下一格。
区间求和 · 加入下标 1(值 2)：把下标 1 上的数 2 加进来。之前累计是 1,加上 2 得到 3。绿色部分就是已经累加进去的范围,紫色是这一帧刚加入的格子。继续往右加下一格。
区间求和 · 加入下标 2(值 3)：把下标 2 上的数 3 加进来。之前累计是 3,加上 3 得到 6。绿色部分就是已经累加进去的范围,紫色是这一帧刚加入的格子。继续往右加下一格。
区间求和 · 加入下标 3(值 3)：把下标 3 上的数 3 加进来。之前累计是 6,加上 3 得到 9。绿色部分就是已经累加进去的范围,紫色是这一帧刚加入的格子。继续往右加下一格。
区间求和 · 加入下标 4(值 4)：把下标 4 上的数 4 加进来。之前累计是 9,加上 4 得到 13。绿色部分就是已经累加进去的范围,紫色是这一帧刚加入的格子。到这,区间里 5 个数全部加完。
完成 · 答案 13：区间求和结束。排序后下标 1 到 5 是 1、2、3、3、4,加起来是 13。本例没有超过取模上限,所以对 10 的 9 次方加 7 取模后还是 13。这就是最终答案。回顾一下全流程:枚举全部子数组和、升序排序、再把指定区间加起来取模,三步走完。
边界想清楚:单元素就取它自己、重复的和都保留、区间覆盖全部时就是所有子数组和的总和。
面试重点:本题规模下直接模拟就够、n 很大时可用前缀和加二分求前 k 小之和、取模只在最后累加时做不能在排序前做。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *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复杂度
- 时间：O(n² log n)，枚举全部子数组和是双重循环,共 n×(n+1)/2 个,约 O(n²);对这约 n² 个数排序是 O(n² log n);区间求和最多扫一遍 O(n²)。三步相加,排序占主导,总体 O(n² log n)
- 空间：O(n²)，主要开销是存放全部子数组和的数组,长度 n×(n+1)/2,峰值 O(n²)。排序本身的额外开销因语言实现而异:C++/Java 递归栈约 O(log n),Python 的 Timsort 最坏 O(n²),但都不会把总空间推到超过 O(n²)
易错点
面试追问把动画讲成自己的话
追问为什么这套直接枚举加排序的做法,在本题约束下是够用的?
追问如果 n 再大很多,有没有更快的办法?
追问为什么累加时要不断取模,而排序和比较时却不取模?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
删除最短的子数组使剩余数组有序
LeetCode 1574 · 中等 · 沿着 二分套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题