题目描述
思路解析动画文字版
记住三步走:枚举出全部子数组和、升序排序、把下标 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题