题目描述
思路解析动画文字版
记住这套路:先排序让相等的值抱团,再扫一遍把等于 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题