题目描述
思路解析
一句话答案：LeetCode 2089 找出数组排序后的目标下标用排序加收集下标：排完序相同值连成一段，从头扫一遍把等于 target 的下标依次收进来即可。时间 O(n log n)、空间 O(1)。
排序之后再找下标，这题到底要返回哪些位置
给一个下标从 0 开始的整数数组 nums 和目标值 target，先把 nums 按非递减（从小到大、允许相等）排好，再返回排序后所有等于 target 的元素所在的下标，按递增排列；一个都没有就返回空列表。题面 nums=[1,2,5,2,3]、target=2 排完是 [1,2,2,3,5]，两个 2 落在下标 1 和 2，答案 [1,2]；换成 target=4，数组里没有 4，返回空列表 []。
在原数组上直接记下标，为什么整个答案都是错的
最容易踩的一步，是拿到 target 就在原数组里数它出现在哪几个下标、直接返回。可题目要的是排序之后的下标：原数组 [1,2,5,2,3] 里两个 2 待在下标 1 和 3，一排序变成 [1,2,2,3,5]，这两个 2 却落到了下标 1 和 2——位置整个挪了。排序前的下标和排序后的下标是两码事，不先排就找，答对纯属碰巧。
排完序之后，相同的值为什么一定连成一段
非递减排序把元素从小到大摆好，等于 target 的那些值大小完全一样，排序时既不会插到比它小的前头、也不会窜到比它大的后头，只能彼此紧挨、连成一整块连续下标。既然它们抱成一团，就用不着东找西找：从下标 0 一路扫到末尾，碰到等于 target 的就把当前下标收进结果，先扫到的下标天然更小，收出来正好是递增顺序。
参考代码就是这两下：nums.sort() 原地排完，再用一句列表推导 [i for i, v in enumerate(nums) if v == target]，把命中的下标全数收下。
排序加一遍扫描，具体是怎么走完的
第一步原地排序，把 nums 变成非递减序列。第二步从左到右扫，用下标 i 遍历每个元素 v：v 等于 target 就记下这个 i；v 小于 target 说明还没扫进目标块、继续往右；v 大于 target 说明已经越过目标块（后面只会更大），剩下的也都不是。扫到头，收集起来的下标列表就是答案；如果一路下来没有一个等于 target，列表始终是空的，直接返回空列表。
拿题面 [1,2,5,2,3]、target=2 亲手走一遍
先排序：[1,2,5,2,3] 变成 [1,2,2,3,5]。再从头往右扫：下标 0 处是 1，比 2 小，跳过；下标 1、2 处都是 2，正好命中，依次收下下标 1 和 2，结果攒成 [1,2]；下标 3 处是 3、下标 4 处是 5，都比 2 大、越过了目标块，跳过。扫完返回 [1,2]，和题面对上。若把 target 换成 4，整趟没有一个等于 4，返回空列表 []。
复杂度卡在排序，还有哪两处收尾容易写反
时间上排序是 O(n log n) 的主导项，后面收集下标只扫一遍是 O(n)，合起来仍是 O(n log n)；空间除去输出列表只用常数个变量，不计排序内部开销是 O(1)。收尾两处别写反：target 不存在时要返回空列表 []，别返回 [-1] 或抛错，题面白纸黑字要的就是空列表；重复的 target 有几个就得收几个下标，别以为相同值只算一个，题面里两个 2 就对应下标 1、2，漏一个答案就短一截。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这套路:先排序让相等的值抱团,再扫一遍把等于 target 的下标一个个收进来。下面先看原始数组长什么样。
原始数组 · 还没排序：这是原始的 nums,一共 8 个数,还没排序。我们要找的目标值是 3。你先扫一眼,3 在这里东一个西一个,毫无规律,直接在原数组上找下标是没有意义的,因为题目要的是排序之后的下标。
排序前 · 目标值 3 散落在下标 1、3、5：把原数组里所有值为 3 的格子标成绿色,它们分别在下标 1、3、5。你看,它们是散开的,中间还夹着别的数。这正是为什么要先排序:排完之后,这三个 3 会被拢到一起。
排序后 · nums 变成非递减：调用语言内置的排序,把 nums 从小到大排好,现在它是 [1,3,3,3,5,6,8,9]。注意看,三个 3 已经紧紧挨在一块了。接下来从下标 0 开始,一格一格往右扫,遇到等于 3 的就把下标收进答案。
扫描下标 0 · 读取 nums[0] = 1：紫色指针走到下标 0,这里的值是 1。拿它和 target 也就是 3 比一比,看是小、是等还是大。
下标 0 · 1 比 3 小,跳过：1 比 3 小,它排在目标块的左边,不是我们要的,标成蓝色跳过。继续往右走。
扫描下标 1 · 读取 nums[1] = 3：紫色指针走到下标 1,这里的值是 3。拿它和 target 也就是 3 比一比,看是小、是等还是大。
下标 1 · 3 命中,收入下标 1：正好等于 3,命中!把下标 1 收进答案,这一格标成绿色。目前收集到 [1]。
扫描下标 2 · 读取 nums[2] = 3：紫色指针走到下标 2,这里的值是 3。拿它和 target 也就是 3 比一比,看是小、是等还是大。
下标 2 · 3 命中,收入下标 2：正好等于 3,命中!把下标 2 收进答案,这一格标成绿色。目前收集到 [1,2]。
扫描下标 3 · 读取 nums[3] = 3：紫色指针走到下标 3,这里的值是 3。拿它和 target 也就是 3 比一比,看是小、是等还是大。
下标 3 · 3 命中,收入下标 3：正好等于 3,命中!把下标 3 收进答案,这一格标成绿色。目前收集到 [1,2,3]。
扫描下标 4 · 读取 nums[4] = 5：紫色指针走到下标 4,这里的值是 5。拿它和 target 也就是 3 比一比,看是小、是等还是大。
下标 4 · 5 比 3 大,后面都更大：5 比 3 大了。因为已经排好序,它右边的数只会更大,再也不会碰到 3,这一格标灰。参考代码是老实扫完的,但你心里要清楚:到这里其实已经可以收工了。
扫描下标 5 · 读取 nums[5] = 6：紫色指针走到下标 5,这里的值是 6。拿它和 target 也就是 3 比一比,看是小、是等还是大。
下标 5 · 6 比 3 大,后面都更大：6 比 3 大了。因为已经排好序,它右边的数只会更大,再也不会碰到 3,这一格标灰。参考代码是老实扫完的,但你心里要清楚:到这里其实已经可以收工了。
扫描下标 6 · 读取 nums[6] = 8：紫色指针走到下标 6,这里的值是 8。拿它和 target 也就是 3 比一比,看是小、是等还是大。
下标 6 · 8 比 3 大,后面都更大：8 比 3 大了。因为已经排好序,它右边的数只会更大,再也不会碰到 3,这一格标灰。参考代码是老实扫完的,但你心里要清楚:到这里其实已经可以收工了。
扫描下标 7 · 读取 nums[7] = 9：紫色指针走到下标 7,这里的值是 9。拿它和 target 也就是 3 比一比,看是小、是等还是大。
下标 7 · 9 比 3 大,后面都更大：9 比 3 大了。因为已经排好序,它右边的数只会更大,再也不会碰到 3,这一格标灰。参考代码是老实扫完的,但你心里要清楚:到这里其实已经可以收工了。
一个更快的观察 · 起始下标 = 比 3 小的元素个数：这里藏着一个更快的思路。比 3 小的元素只有 1 个,就是那个 1,所以排序后第一个 3 一定落在下标 1。目标块从下标 1 起头,一共 3 个 3,于是下标就是 1、2、3。顺着这个观察,其实连排序都能省掉,后面面试环节细说。
最终答案 · 目标下标 [1,2,3]：扫完全程,绿色的三格就是等于 3 的位置,下标依次是 1、2、3。所以答案是 [1,2,3],和我们一开始说的对上了。左边蓝色的更小、右边灰色的更大,绿色这一块就是目标下标。
边界想清:单元素命中记 [0]、目标不存在返回空列表、全部相等则每个下标都收。
面试重点:排序法 O(n log n) 直接明了;计数 less 和 equal 可优化到 O(n),起始下标等于比 target 小的个数。
参考代码
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 targetIndices(self, nums: List[int], target: int) -> List[int]: nums.sort() return [i for i, v in enumerate(nums) if v == target]复杂度
- 时间：O(n log n)，排序是主导,n 个元素排序要 O(n log n);后面从头扫一遍收集下标是 O(n),加起来仍是 O(n log n)
- 空间：不计排序 O(1);计入排序 C plus plus / Java O(log n),Python 最坏 O(n)，除去输出列表,只用常数个辅助变量。若把排序内部开销计入:C plus plus 与 Java 的排序递归栈约 O(log n),Python 的 Timsort 最坏 O(n);不计排序则 O(1)
易错点
面试追问把动画讲成自己的话
追问能不能不排序,做到 O(n)?
追问为什么目标块的起始下标正好等于比 target 小的元素个数?
追问这题的时间复杂度卡在哪?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
统计和小于目标的下标对数目
LeetCode 2824 · 简单 · 沿着 二分套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题