LeetCode 1630中等贪心 · 排序

等差子数组图解题解

这道题到底在问什么

先把题意看清。等差数列的意思是:数列里每相邻两个数的差都一样,比如 3、5、7、9 相邻差都是 2,就是等差。题目给一个数组 nums,再给两个等长数组 l 和 r,每一对 l[i]、r[i] 表示一组范围查询。对第 i 组,要判断子数组 nums[l[i]] 到 nums[r[i]] 能不能重新排列成等差数列,能就 answer[i] = true,否则 false。注意是「能不能重排」,所以原来的顺序不重要,我们有权先把这段排好序再看。数据范围:数组长度 2 ≤ n ≤ 500,查询组数 1 ≤ m ≤ 500,元素可正可负。本节盯着 nums = [4,6,5,9,3,7],查询 l = [0,0,2]、r = [2,3,5],一组一组判,最后答案是 [true, false, true]。

输入: nums=[4,6,5,9,3,7], [l,r]=[0,2]
输出: true · [4,6,5] 可排成 4,5,6
输入: nums=[4,6,5,9,3,7], [l,r]=[0,3]
输出: false · [4,6,5,9] 排不成等差
输入: nums=[4,6,5,9,3,7], [l,r]=[2,5]
输出: true · [5,9,3,7] 可排成 3,5,7,9

最优解：一步一步想明白

3核心一句:把子数组升序排好,公差 d = sorted[1]-sorted[0],再逐对查相邻差是否都等于 d。全相等就能重排成等差数列(true),有一对不等就 false。下面每组查询都套这套。
4先看清画面。上面是源数组 nums = [4,6,5,9,3,7],下标从 0 到 5。我们有 3 组范围查询:[0,2]、[0,3]、[2,5]。每一组就是把对应下标这一段数取出来,判断它能不能重排成等差数列。下面一组一组来,先看第 0 组。
5第 0 组查询,范围是 [0,2]。把下标 0 到 2 这一段从源数组里圈出来,得到子数组 [4,6,5]。其余下标这次用不上,先按灰色搁一边。接下来要判断这 3 个数能不能重排成等差数列。
6把刚取出的 [4,6,5] 升序排好,变成 [4,5,6]。既然题目允许重排,排序就是最省心的摆法:如果它真是等差数列,排完之后相邻间隔就该处处一样。现在最小的 4 在最左,最大的 6 在最右。
7先用最前面两个数定下公差。d = 排序后第 1 个减第 0 个 = 5 减 4 = 1。如果这一段是等差数列,那么往后每一对相邻数的差,都得严丝合缝地等于这个 1。下面就从左到右一对一对地查。
8看第 1 对相邻数 4 和 5,它俩的差是 5 减 4 = 1,正好等于公差 1。这一对过关,标成绿色,继续往右查下一对。
9看第 2 对相邻数 5 和 6,它俩的差是 6 减 5 = 1,正好等于公差 1。这一对过关,标成绿色。到这里这一段两对差都查完了,都等于公差 1。
10从头到尾每一对相邻差都等于 1,整段绿透了。说明 [4,5,6] 本身就是个公差为 1 的等差数列,原来的 [4,6,5] 当然能重排成它。第 0 组答案是 true。
11第 1 组查询,范围是 [0,3]。把下标 0 到 3 这一段从源数组里圈出来,得到子数组 [4,6,5,9]。其余下标这次用不上,先按灰色搁一边。接下来要判断这 4 个数能不能重排成等差数列。
12把刚取出的 [4,6,5,9] 升序排好,变成 [4,5,6,9]。既然题目允许重排,排序就是最省心的摆法:如果它真是等差数列,排完之后相邻间隔就该处处一样。现在最小的 4 在最左,最大的 9 在最右。
13先用最前面两个数定下公差。d = 排序后第 1 个减第 0 个 = 5 减 4 = 1。如果这一段是等差数列,那么往后每一对相邻数的差,都得严丝合缝地等于这个 1。下面就从左到右一对一对地查。
14看第 1 对相邻数 4 和 5,它俩的差是 5 减 4 = 1,正好等于公差 1。这一对过关,标成绿色,继续往右查下一对。
15看第 2 对相邻数 5 和 6,它俩的差是 6 减 5 = 1,正好等于公差 1。这一对过关,标成绿色,继续往右查下一对。
16看第 3 对相邻数 6 和 9,差是 9 减 6 = 3,可公差是 1,这一对对不上。出现了一个不相等的差,标红。等差数列要求处处相等,只要有一处不符就彻底没戏,这组直接判 false,后面不用再查了。
17问题出在那对红色的数上:它们的差是 3,跟公差 1 对不上。哪怕前面几对都齐整,只要有一处断了节奏,这段就排不成等差数列。所以 [4,6,5,9] 不行,第 1 组答案是 false。
18第 2 组查询,范围是 [2,5]。把下标 2 到 5 这一段从源数组里圈出来,得到子数组 [5,9,3,7]。其余下标这次用不上,先按灰色搁一边。接下来要判断这 4 个数能不能重排成等差数列。
19把刚取出的 [5,9,3,7] 升序排好,变成 [3,5,7,9]。既然题目允许重排,排序就是最省心的摆法:如果它真是等差数列,排完之后相邻间隔就该处处一样。现在最小的 3 在最左,最大的 9 在最右。
20先用最前面两个数定下公差。d = 排序后第 1 个减第 0 个 = 5 减 3 = 2。如果这一段是等差数列,那么往后每一对相邻数的差,都得严丝合缝地等于这个 2。下面就从左到右一对一对地查。
21看第 1 对相邻数 3 和 5,它俩的差是 5 减 3 = 2,正好等于公差 2。这一对过关,标成绿色,继续往右查下一对。
22看第 2 对相邻数 5 和 7,它俩的差是 7 减 5 = 2,正好等于公差 2。这一对过关,标成绿色,继续往右查下一对。
23看第 3 对相邻数 7 和 9,它俩的差是 9 减 7 = 2,正好等于公差 2。这一对过关,标成绿色。到这里这一段三对差都查完了,都等于公差 2。
24从头到尾每一对相邻差都等于 2,整段绿透了。说明 [3,5,7,9] 本身就是个公差为 2 的等差数列,原来的 [5,9,3,7] 当然能重排成它。第 2 组答案是 true。
25三组查询都判完了,回看一遍:第 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]。每一组都是同一套:取出、排序、逐对查公差。

⚠️ 容易写错的地方

✗ 错：不排序就直接拿原始相邻两数算差,认为差不一样就不是等差

✓ 对：题目允许重排,必须先把这段升序排好,再看排序后的相邻差

原始顺序毫无意义,[4,6,5] 原序相邻差是 2 和 -1,看着乱,但重排成 4,5,6 就是等差。判定只看「能否重排成等差」,所以必须先排序,拿排好序的相邻差去比

✗ 错：公差只用前两个数定一次,后面就不再逐对核对了

✓ 对：定下 d 后,要从左到右每一对相邻数都核对差是否等于 d

只看头两个数定 d 远远不够,后面任何一对断了节奏都不算等差。比如排序后 4,5,6,9,前两对差是 1,可 6 到 9 差是 3,必须查到这一对才暴露问题,漏查就会误判成 true

✗ 错：子数组只有两个数时纠结公差,甚至判成 false

✓ 对：长度为 2 的子数组永远是等差数列,直接 true

两个数只有一个间隔,这一个差自己跟自己当然相等,天然满足等差定义。所以任意两个数都能排成等差,这种最短情况要当成恒为 true,别被绕进去

完整代码（Python / C++ / Java）

Python

from __future__ import annotations
from 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)]

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {
        vector<bool> ans;
        auto check = [](vector<int>& nums, int l, int r) {
            unordered_set<int> s;
            int n = r - l + 1;
            int a1 = 1 << 30, an = -a1;
            for (int i = l; i <= r; ++i) {
                s.insert(nums[i]);
                a1 = min(a1, nums[i]);
                an = max(an, nums[i]);
            }
            if ((an - a1) % (n - 1)) {
                return false;
            }
            int d = (an - a1) / (n - 1);
            for (int i = 1; i < n; ++i) {
                if (!s.count(a1 + (i - 1) * d)) {
                    return false;
                }
            }
            return true;
        };
        for (int i = 0; i < l.size(); ++i) {
            ans.push_back(check(nums, l[i], r[i]));
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public List<Boolean> checkArithmeticSubarrays(int[] nums, int[] l, int[] r) {
        List<Boolean> ans = new ArrayList<>();
        for (int i = 0; i < l.length; ++i) {
            ans.add(check(nums, l[i], r[i]));
        }
        return ans;
    }

    private boolean check(int[] nums, int l, int r) {
        Set<Integer> s = new HashSet<>();
        int n = r - l + 1;
        int a1 = 1 << 30, an = -a1;
        for (int i = l; i <= r; ++i) {
            s.add(nums[i]);
            a1 = Math.min(a1, nums[i]);
            an = Math.max(an, nums[i]);
        }
        if ((an - a1) % (n - 1) != 0) {
            return false;
        }
        int d = (an - a1) / (n - 1);
        for (int i = 1; i < n; ++i) {
            if (!s.contains(a1 + (i - 1) * d)) {
                return false;
            }
        }
        return true;
    }
}

复杂度

时间

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 无关(答案数组属于必须返回的输出,不计入额外空间)

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着等差子数组的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

为什么判断「能否重排成等差」可以先排序?会不会漏掉某种排法?+

不会漏。等差数列有个铁性质:它一旦成立,把它的元素从小到大排,就正好是这个等差数列本身(公差为正时)或它的倒序(公差为负时),相邻差的绝对值处处相等。也就是说,如果这堆数真能排成等差,那升序排列必定是一种合法排法。所以只要升序排完看相邻差是否恒定,就能一次性判定,不必去枚举所有排列。反过来,如果升序排完相邻差都不恒定,任何别的排法更不可能恒定,直接 false。

参考代码不排序,用最小最大值加哈希集合,凭什么也对?+

凭等差数列的结构。若这 n 个数能排成等差,排好后最小的是首项 a1、最大的是末项 an,中间 n 减 1 个间隔均分,所以公差必然是 (an 减 a1) 除以 (n 减 1),先要求这个除法能整除,否则直接否。整除后得到 d,那么 a1、a1 加 d、a1 加 2d 一直到 an 这 n 个「应该出现的值」必须恰好就是这堆数。把这堆数放进哈希集合,逐个查这些应出现的值在不在集合里,全在就成立。它用 O(k) 的最值加哈希替代了 O(k log k) 的排序,思路和排序法等价。

如果子数组里有重复元素,这套判断还成立吗?+

要看情况。排序法天然能处理重复:比如 [7,7,7] 排完还是 7,7,7,公差 0、处处相等,是合法等差。但参考代码的哈希集合法要当心,集合会把重复值去重,像 [1,1,3] 这种,a1 等于 1、an 等于 3、n 等于 3,公差按 (3 减 1) 除以 2 算出来是 1,它会去查 1、2、3 在不在集合里,而 2 不在,正确地判 false。只要题目里同一段内有重复且会影响等差结构,集合去重反而帮我们把不合法的情况筛掉了,结论依然正确。

想听吴师兄把这道题讲给你听？

文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把等差子数组一步步讲透（全站 0 节语音精讲，持续扩充），卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

LeetCode 1630中等贪心 · 排序

等差子数组图解题解

这道题到底在问什么

输入: nums=[4,6,5,9,3,7], [l,r]=[0,2]
输出: true · [4,6,5] 可排成 4,5,6
输入: nums=[4,6,5,9,3,7], [l,r]=[0,3]
输出: false · [4,6,5,9] 排不成等差
输入: nums=[4,6,5,9,3,7], [l,r]=[2,5]
输出: true · [5,9,3,7] 可排成 3,5,7,9

最优解：一步一步想明白

3核心一句:把子数组升序排好,公差 d = sorted[1]-sorted[0],再逐对查相邻差是否都等于 d。全相等就能重排成等差数列(true),有一对不等就 false。下面每组查询都套这套。
4先看清画面。上面是源数组 nums = [4,6,5,9,3,7],下标从 0 到 5。我们有 3 组范围查询:[0,2]、[0,3]、[2,5]。每一组就是把对应下标这一段数取出来,判断它能不能重排成等差数列。下面一组一组来,先看第 0 组。
5第 0 组查询,范围是 [0,2]。把下标 0 到 2 这一段从源数组里圈出来,得到子数组 [4,6,5]。其余下标这次用不上,先按灰色搁一边。接下来要判断这 3 个数能不能重排成等差数列。
6把刚取出的 [4,6,5] 升序排好,变成 [4,5,6]。既然题目允许重排,排序就是最省心的摆法:如果它真是等差数列,排完之后相邻间隔就该处处一样。现在最小的 4 在最左,最大的 6 在最右。
7先用最前面两个数定下公差。d = 排序后第 1 个减第 0 个 = 5 减 4 = 1。如果这一段是等差数列,那么往后每一对相邻数的差,都得严丝合缝地等于这个 1。下面就从左到右一对一对地查。
8看第 1 对相邻数 4 和 5,它俩的差是 5 减 4 = 1,正好等于公差 1。这一对过关,标成绿色,继续往右查下一对。
9看第 2 对相邻数 5 和 6,它俩的差是 6 减 5 = 1,正好等于公差 1。这一对过关,标成绿色。到这里这一段两对差都查完了,都等于公差 1。
10从头到尾每一对相邻差都等于 1,整段绿透了。说明 [4,5,6] 本身就是个公差为 1 的等差数列,原来的 [4,6,5] 当然能重排成它。第 0 组答案是 true。
11第 1 组查询,范围是 [0,3]。把下标 0 到 3 这一段从源数组里圈出来,得到子数组 [4,6,5,9]。其余下标这次用不上,先按灰色搁一边。接下来要判断这 4 个数能不能重排成等差数列。
12把刚取出的 [4,6,5,9] 升序排好,变成 [4,5,6,9]。既然题目允许重排,排序就是最省心的摆法:如果它真是等差数列,排完之后相邻间隔就该处处一样。现在最小的 4 在最左,最大的 9 在最右。
13先用最前面两个数定下公差。d = 排序后第 1 个减第 0 个 = 5 减 4 = 1。如果这一段是等差数列,那么往后每一对相邻数的差,都得严丝合缝地等于这个 1。下面就从左到右一对一对地查。
14看第 1 对相邻数 4 和 5,它俩的差是 5 减 4 = 1,正好等于公差 1。这一对过关,标成绿色,继续往右查下一对。
15看第 2 对相邻数 5 和 6,它俩的差是 6 减 5 = 1,正好等于公差 1。这一对过关,标成绿色,继续往右查下一对。
16看第 3 对相邻数 6 和 9,差是 9 减 6 = 3,可公差是 1,这一对对不上。出现了一个不相等的差,标红。等差数列要求处处相等,只要有一处不符就彻底没戏,这组直接判 false,后面不用再查了。
17问题出在那对红色的数上:它们的差是 3,跟公差 1 对不上。哪怕前面几对都齐整,只要有一处断了节奏,这段就排不成等差数列。所以 [4,6,5,9] 不行,第 1 组答案是 false。
18第 2 组查询,范围是 [2,5]。把下标 2 到 5 这一段从源数组里圈出来,得到子数组 [5,9,3,7]。其余下标这次用不上,先按灰色搁一边。接下来要判断这 4 个数能不能重排成等差数列。
19把刚取出的 [5,9,3,7] 升序排好,变成 [3,5,7,9]。既然题目允许重排,排序就是最省心的摆法:如果它真是等差数列,排完之后相邻间隔就该处处一样。现在最小的 3 在最左,最大的 9 在最右。
20先用最前面两个数定下公差。d = 排序后第 1 个减第 0 个 = 5 减 3 = 2。如果这一段是等差数列,那么往后每一对相邻数的差,都得严丝合缝地等于这个 2。下面就从左到右一对一对地查。
21看第 1 对相邻数 3 和 5,它俩的差是 5 减 3 = 2,正好等于公差 2。这一对过关,标成绿色,继续往右查下一对。
22看第 2 对相邻数 5 和 7,它俩的差是 7 减 5 = 2,正好等于公差 2。这一对过关,标成绿色,继续往右查下一对。
23看第 3 对相邻数 7 和 9,它俩的差是 9 减 7 = 2,正好等于公差 2。这一对过关,标成绿色。到这里这一段三对差都查完了,都等于公差 2。
24从头到尾每一对相邻差都等于 2,整段绿透了。说明 [3,5,7,9] 本身就是个公差为 2 的等差数列,原来的 [5,9,3,7] 当然能重排成它。第 2 组答案是 true。
25三组查询都判完了,回看一遍:第 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]。每一组都是同一套:取出、排序、逐对查公差。

⚠️ 容易写错的地方

✗ 错：不排序就直接拿原始相邻两数算差,认为差不一样就不是等差

✓ 对：题目允许重排,必须先把这段升序排好,再看排序后的相邻差

原始顺序毫无意义,[4,6,5] 原序相邻差是 2 和 -1,看着乱,但重排成 4,5,6 就是等差。判定只看「能否重排成等差」,所以必须先排序,拿排好序的相邻差去比

✗ 错：公差只用前两个数定一次,后面就不再逐对核对了

✓ 对：定下 d 后,要从左到右每一对相邻数都核对差是否等于 d

✗ 错：子数组只有两个数时纠结公差,甚至判成 false

✓ 对：长度为 2 的子数组永远是等差数列,直接 true

两个数只有一个间隔,这一个差自己跟自己当然相等,天然满足等差定义。所以任意两个数都能排成等差,这种最短情况要当成恒为 true,别被绕进去

完整代码（Python / C++ / Java）

Python

from __future__ import annotations
from 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)]

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {
        vector<bool> ans;
        auto check = [](vector<int>& nums, int l, int r) {
            unordered_set<int> s;
            int n = r - l + 1;
            int a1 = 1 << 30, an = -a1;
            for (int i = l; i <= r; ++i) {
                s.insert(nums[i]);
                a1 = min(a1, nums[i]);
                an = max(an, nums[i]);
            }
            if ((an - a1) % (n - 1)) {
                return false;
            }
            int d = (an - a1) / (n - 1);
            for (int i = 1; i < n; ++i) {
                if (!s.count(a1 + (i - 1) * d)) {
                    return false;
                }
            }
            return true;
        };
        for (int i = 0; i < l.size(); ++i) {
            ans.push_back(check(nums, l[i], r[i]));
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public List<Boolean> checkArithmeticSubarrays(int[] nums, int[] l, int[] r) {
        List<Boolean> ans = new ArrayList<>();
        for (int i = 0; i < l.length; ++i) {
            ans.add(check(nums, l[i], r[i]));
        }
        return ans;
    }

    private boolean check(int[] nums, int l, int r) {
        Set<Integer> s = new HashSet<>();
        int n = r - l + 1;
        int a1 = 1 << 30, an = -a1;
        for (int i = l; i <= r; ++i) {
            s.add(nums[i]);
            a1 = Math.min(a1, nums[i]);
            an = Math.max(an, nums[i]);
        }
        if ((an - a1) % (n - 1) != 0) {
            return false;
        }
        int d = (an - a1) / (n - 1);
        for (int i = 1; i < n; ++i) {
            if (!s.contains(a1 + (i - 1) * d)) {
                return false;
            }
        }
        return true;
    }
}

复杂度

时间

O(m · k)

空间

O(k)

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着等差子数组的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

为什么判断「能否重排成等差」可以先排序?会不会漏掉某种排法?+

参考代码不排序,用最小最大值加哈希集合,凭什么也对?+

如果子数组里有重复元素,这套判断还成立吗?+

想听吴师兄把这道题讲给你听？

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

等差子数组 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

等差子数组 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

等差子数组图解题解

等差子数组图解题解