题目描述
思路解析动画文字版
核心一句:把子数组升序排好,公差 d = sorted[1]-sorted[0],再逐对查相邻差是否都等于 d。全相等就能重排成等差数列(true),有一对不等就 false。下面每组查询都套这套。
总览 · 源数组 + 3 组范围查询：先看清画面。上面是源数组 nums = [4,6,5,9,3,7],下标从 0 到 5。我们有 3 组范围查询:[0,2]、[0,3]、[2,5]。每一组就是把对应下标这一段数取出来,判断它能不能重排成等差数列。下面一组一组来,先看第 0 组。
第 0 组 · 取出 nums[0..2]：第 0 组查询,范围是 [0,2]。把下标 0 到 2 这一段从源数组里圈出来,得到子数组 [4,6,5]。其余下标这次用不上,先按灰色搁一边。接下来要判断这 3 个数能不能重排成等差数列。
第 0 组 · 升序排序：把刚取出的 [4,6,5] 升序排好,变成 [4,5,6]。既然题目允许重排,排序就是最省心的摆法:如果它真是等差数列,排完之后相邻间隔就该处处一样。现在最小的 4 在最左,最大的 6 在最右。
第 0 组 · 定公差 d = 1：先用最前面两个数定下公差。d = 排序后第 1 个减第 0 个 = 5 减 4 = 1。如果这一段是等差数列,那么往后每一对相邻数的差,都得严丝合缝地等于这个 1。下面就从左到右一对一对地查。
第 0 组 · 第 1 对差 = 1 等于 d：看第 1 对相邻数 4 和 5,它俩的差是 5 减 4 = 1,正好等于公差 1。这一对过关,标成绿色,继续往右查下一对。
第 0 组 · 第 2 对差 = 1 等于 d：看第 2 对相邻数 5 和 6,它俩的差是 6 减 5 = 1,正好等于公差 1。这一对过关,标成绿色。到这里这一段两对差都查完了,都等于公差 1。
第 0 组 · 判定 true：从头到尾每一对相邻差都等于 1,整段绿透了。说明 [4,5,6] 本身就是个公差为 1 的等差数列,原来的 [4,6,5] 当然能重排成它。第 0 组答案是 true。
第 1 组 · 取出 nums[0..3]：第 1 组查询,范围是 [0,3]。把下标 0 到 3 这一段从源数组里圈出来,得到子数组 [4,6,5,9]。其余下标这次用不上,先按灰色搁一边。接下来要判断这 4 个数能不能重排成等差数列。
第 1 组 · 升序排序：把刚取出的 [4,6,5,9] 升序排好,变成 [4,5,6,9]。既然题目允许重排,排序就是最省心的摆法:如果它真是等差数列,排完之后相邻间隔就该处处一样。现在最小的 4 在最左,最大的 9 在最右。
第 1 组 · 定公差 d = 1：先用最前面两个数定下公差。d = 排序后第 1 个减第 0 个 = 5 减 4 = 1。如果这一段是等差数列,那么往后每一对相邻数的差,都得严丝合缝地等于这个 1。下面就从左到右一对一对地查。
第 1 组 · 第 1 对差 = 1 等于 d：看第 1 对相邻数 4 和 5,它俩的差是 5 减 4 = 1,正好等于公差 1。这一对过关,标成绿色,继续往右查下一对。
第 1 组 · 第 2 对差 = 1 等于 d：看第 2 对相邻数 5 和 6,它俩的差是 6 减 5 = 1,正好等于公差 1。这一对过关,标成绿色,继续往右查下一对。
第 1 组 · 第 3 对差 = 3 不等于 d：看第 3 对相邻数 6 和 9,差是 9 减 6 = 3,可公差是 1,这一对对不上。出现了一个不相等的差,标红。等差数列要求处处相等,只要有一处不符就彻底没戏,这组直接判 false,后面不用再查了。
第 1 组 · 判定 false：问题出在那对红色的数上:它们的差是 3,跟公差 1 对不上。哪怕前面几对都齐整,只要有一处断了节奏,这段就排不成等差数列。所以 [4,6,5,9] 不行,第 1 组答案是 false。
第 2 组 · 取出 nums[2..5]：第 2 组查询,范围是 [2,5]。把下标 2 到 5 这一段从源数组里圈出来,得到子数组 [5,9,3,7]。其余下标这次用不上,先按灰色搁一边。接下来要判断这 4 个数能不能重排成等差数列。
第 2 组 · 升序排序：把刚取出的 [5,9,3,7] 升序排好,变成 [3,5,7,9]。既然题目允许重排,排序就是最省心的摆法:如果它真是等差数列,排完之后相邻间隔就该处处一样。现在最小的 3 在最左,最大的 9 在最右。
第 2 组 · 定公差 d = 2：先用最前面两个数定下公差。d = 排序后第 1 个减第 0 个 = 5 减 3 = 2。如果这一段是等差数列,那么往后每一对相邻数的差,都得严丝合缝地等于这个 2。下面就从左到右一对一对地查。
第 2 组 · 第 1 对差 = 2 等于 d：看第 1 对相邻数 3 和 5,它俩的差是 5 减 3 = 2,正好等于公差 2。这一对过关,标成绿色,继续往右查下一对。
第 2 组 · 第 2 对差 = 2 等于 d：看第 2 对相邻数 5 和 7,它俩的差是 7 减 5 = 2,正好等于公差 2。这一对过关,标成绿色,继续往右查下一对。
第 2 组 · 第 3 对差 = 2 等于 d：看第 3 对相邻数 7 和 9,它俩的差是 9 减 7 = 2,正好等于公差 2。这一对过关,标成绿色。到这里这一段三对差都查完了,都等于公差 2。
第 2 组 · 判定 true：从头到尾每一对相邻差都等于 2,整段绿透了。说明 [3,5,7,9] 本身就是个公差为 2 的等差数列,原来的 [5,9,3,7] 当然能重排成它。第 2 组答案是 true。
完成 · answer = [true, false, true]：三组查询都判完了,回看一遍:第 0 组 [4,6,5] 排成 4,5,6,公差 1,成立,true;第 1 组 [4,6,5,9] 排成 4,5,6,9,到 6 和 9 那对差变成 3,断了,false;第 2 组 [5,9,3,7] 排成 3,5,7,9,公差 2,处处相等,true。最终答案就是 [true, false, true]。每一组都是同一套:取出、排序、逐对查公差。
边界:长度为 2 恒 true;全相等时公差 0 也是等差(true);含负数排序后照常查差,如 [3,-1,-5] 排成 -5,-1,3 公差 4。
面试重点:能否重排成等差只需看升序后相邻差是否恒定(升序必是一种合法排法);参考代码用最小最大值定公差加哈希验证等差项,O(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 checkArithmeticSubarrays( self, nums: List[int], l: List[int], r: List[int] ) -> List[bool]: def check(nums, l, r): n = r - l + 1 s = set(nums[l : l + n]) a1, an = min(nums[l : l + n]), max(nums[l : l + n]) d, mod = divmod(an - a1, n - 1) return mod == 0 and all((a1 + (i - 1) * d) in s for i in range(1, n)) return [check(nums, left, right) for left, right in zip(l, r)]复杂度
- 时间：O(m · k)，m 是查询组数,k 是单段子数组的长度。参考代码对每组查询扫一遍这段数求最小最大值、建哈希集合,再验证 k 个等差项是否在集合里,都是 O(k);m 组合起来是 O(m·k)。本节演示里我们为直观用了排序,单组排序是 O(k log k),但参考代码用最小最大值加哈希集合省掉了排序,把单组压到 O(k)
- 空间：O(k)，按峰值算。处理每一组查询时,要把这一段 k 个数装进一个哈希集合,占用 O(k);组与组之间集合可以复用或重建,不会叠加。所以额外空间是单段最大长度量级的 O(k),与查询组数 m 无关(答案数组属于必须返回的输出,不计入额外空间)
易错点
面试追问把动画讲成自己的话
追问为什么判断「能否重排成等差」可以先排序?会不会漏掉某种排法?
追问参考代码不排序,用最小最大值加哈希集合,凭什么也对?
追问如果子数组里有重复元素,这套判断还成立吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
字符频次唯一的最小删除次数
LeetCode 1647 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题