题目描述
思路解析
一句话答案：LeetCode 1389 按既定顺序创建目标数组：从空数组出发，按顺序把 nums[i] 插到下标 index[i]，插入会把该位置起的元素右移腾位——直接模拟即可，时间 O(n²)、空间 O(n)。
target 从空数组开始，最后要长成什么样
给两个等长的数组 nums 和 index。target 一开始是空的，按从左到右一对一对地读：把 nums[i] 插到 target 的下标 index[i] 处，插完返回 target。题面 nums=[1,2,3]、index=[0,0,0] 得 [3,2,1]，nums=[4,5,6,7]、index=[0,1,1,2] 得 [4,6,7,5]——同样几个值，位置不同，结果差得远。
别把插入当成覆盖赋值
看到「下标 index[i] 处放 nums[i]」，不少人第一反应写 target[index[i]] = nums[i]。但这是覆盖，会盖掉原有的值、长度不变。题目要的是插入：在 index[i] 塞进新元素，原来这格及右边的元素整块让位，长度加一。往 [0,1,2] 的下标 2 插 3，插入得 [0,1,3,2]，覆盖却得 [0,1,3]、全错。
「插入」把哪些元素挪走了
要在下标 k 放新元素，得先腾出这一格——把当前占着下标 k 到末尾的元素整体往右挪一格，下标 k 空出来，再放新值，长度加一。注意是「k 及右边所有元素」一起右移，不是只动一个。有种情况不用挪：index[i] 等于 target 当前长度时，插入点在末尾之后，没有元素挡路，直接接尾。
每步该接尾还是腾位
过程是一个循环：按 i 递增取出 nums[i] 和 index[i]，在下标 index[i] 插入一次。每步只看插入点和当前长度的关系——等于长度就接尾，一个都不挪；比长度小就插到中间，把该位置起的元素右移腾位。参考代码 target.insert(i, x) 一行就替你封装好右移，但心里要清楚它挪了哪些格。
题面两组示例各手插一遍
先走 nums=[1,2,3]、index=[0,0,0]。target=[]，插 1 到下标 0 接尾得 [1]；插 2 到下标 0，1 右移一格，2 落到开头得 [2,1]；插 3 到下标 0，2 和 1 一起右移得 [3,2,1]。三次头插等于把序列倒过来。
再走 nums=[4,5,6,7]、index=[0,1,1,2]。插 4 到下标 0 得 [4]；插 5 到下标 1 正等于长度 1，接尾得 [4,5]；插 6 到下标 1，5 右移一格，6 挤进得 [4,6,5]；插 7 到下标 2，5 再右移一格，最终得 [4,6,7,5]。
越界的担心其实多余，一次插入有多贵
一共 n 次插入，往连续数组中间插入平均要把后面约 n 个元素右移一格，单次 O(n)，合起来 O(n²)；空间 O(n)（Java 版把 ArrayList 转 int[] 多一份 O(n) 临时开销，不改量级）。n 最多 100 毫无压力。边界替你验理解：nums=[1]、index=[0] 只插一次得 [1]；index 全填 0 是不停头插、把 nums 倒过来；index 一路递增全是接尾，原样保留 nums 顺序。别慌，index[i] 等于当前长度并非越界，是合法接尾。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢一句:从空列表开始,按顺序把 nums[i] 插到下标 index[i],插入会把该位置起的元素右移腾位。下面每帧都在套这句。
总览 · 空 target + 输入队列：target 现在是个空数组,右边侧栏是输入队列,把要插入的五对 (值 → 位置) 都列了出来:0 到位置 0、1 到位置 1、2 到位置 2、3 到位置 2、4 到位置 1。我们就按这个顺序一对一对地往 target 里插,每插一次它就长一格。先从第 0 步开始。
第 0 步 · 读 (值 0, 位置 0)：第 0 步,从输入队列读出这一对:要把值 0 插到下标 0。此刻 target 是 [],长度 0。
第 0 步 · 定位下标 0：插入下标是 0,正好等于 target 当前长度 0,说明这一格就在末尾的后面,属于接尾,后面没有元素挡路。
第 0 步 · 接尾免移动：接尾这种情况最省事,后面是空的,不用挪任何元素,直接把 0 放到末尾就好。
第 0 步 · 插入完成：把 0 放进空出来的下标 0,绿色就是它的新位置。target 现在变成 [0],长度涨到 1。已经插入 1 个,继续下一对。
第 1 步 · 读 (值 1, 位置 1)：第 1 步,从输入队列读出这一对:要把值 1 插到下标 1。此刻 target 是 [0],长度 1。
第 1 步 · 定位下标 1：插入下标是 1,正好等于 target 当前长度 1,说明这一格就在末尾的后面,属于接尾,后面没有元素挡路。
第 1 步 · 接尾免移动：接尾这种情况最省事,后面是空的,不用挪任何元素,直接把 1 放到末尾就好。
第 1 步 · 插入完成：把 1 放进空出来的下标 1,绿色就是它的新位置。target 现在变成 [0,1],长度涨到 2。已经插入 2 个,继续下一对。
第 2 步 · 读 (值 2, 位置 2)：第 2 步,从输入队列读出这一对:要把值 2 插到下标 2。此刻 target 是 [0,1],长度 2。
第 2 步 · 定位下标 2：插入下标是 2,正好等于 target 当前长度 2,说明这一格就在末尾的后面,属于接尾,后面没有元素挡路。
第 2 步 · 接尾免移动：接尾这种情况最省事,后面是空的,不用挪任何元素,直接把 2 放到末尾就好。
第 2 步 · 插入完成：把 2 放进空出来的下标 2,绿色就是它的新位置。target 现在变成 [0,1,2],长度涨到 3。已经插入 3 个,继续下一对。
第 3 步 · 读 (值 3, 位置 2)：第 3 步,从输入队列读出这一对:要把值 3 插到下标 2。此刻 target 是 [0,1,2],长度 3。
第 3 步 · 定位下标 2：插入下标是 2,比当前长度 3 小,说明要插到中间。紫色指针指着下标 2,这是 3 要落脚的位置,可它现在被占着,得先腾地方。
第 3 步 · 右移腾位：蓝色标出的这 1 个元素,原本占着下标 2 到 2,现在它们整体往右挪一格,空出下标 2 这个位置。这一步右移就是插入的代价所在。
第 3 步 · 插入完成：把 3 放进空出来的下标 2,绿色就是它的新位置。target 现在变成 [0,1,3,2],长度涨到 4。已经插入 4 个,继续下一对。
第 4 步 · 读 (值 4, 位置 1)：第 4 步,从输入队列读出这一对:要把值 4 插到下标 1。此刻 target 是 [0,1,3,2],长度 4。
第 4 步 · 定位下标 1：插入下标是 1,比当前长度 4 小,说明要插到中间。紫色指针指着下标 1,这是 4 要落脚的位置,可它现在被占着,得先腾地方。
第 4 步 · 右移腾位：蓝色标出的这 3 个元素,原本占着下标 1 到 3,现在它们整体往右挪一格,空出下标 1 这个位置。这一步右移就是插入的代价所在。
第 4 步 · 插入完成：把 4 放进空出来的下标 1,绿色就是它的新位置。target 现在变成 [0,4,1,3,2],长度涨到 5。已经插入 5 个,全部插完了。
完成 · target = [0,4,1,3,2]：五对都插完了,回看一遍:0、1、2 这三步插入点都正好在末尾,直接接尾;第 3 步把 3 插到下标 2,把原来的 2 挤到右边;第 4 步把 4 插到下标 1,又把 1、3、2 整体右移。最终 target 就是 [0,4,1,3,2],跟开头说的一字不差。整个过程就是照规则一步步插,没有任何技巧。
边界:单元素直接得自身;index 全 0 等于不断头插会把序列翻转;index 递增全接尾则保持原顺序。
面试重点:连续数组中间插入致 O(n²),换链表也快不了;index 范围 0 到当前长度故不越界;Java 要多一步 ArrayList 转 int[]。
参考代码
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 TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def createTargetArray(self, nums: List[int], index: List[int]) -> List[int]: target = [] for x, i in zip(nums, index): target.insert(i, x) return target复杂度
- 时间：O(n²)，n 是 nums 的长度。一共要做 n 次插入,而往一个连续数组的中间插入,平均要把后面约 n 个元素右移一格,单次是 O(n),n 次合起来就是 O(n²)。本题 n 最大只有 100,这个量级毫无压力
- 空间：O(n)，总体空间 O(n),target 最终要装下全部 n 个元素。Python 和 C++ 直接把构造出来的容器作为返回结果,除它之外只用常数个循环变量;Java 这版先用 ArrayList 存完整 target 再转成返回的 int[],会有一份 O(n) 临时列表加数组转换,常数倍不改变总体 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么这道题的时间复杂度是 O(n²),能更快吗?
追问插入下标 index[i] 的取值范围是什么,为什么不会越界?
追问三种语言实现上有什么需要注意的差别?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
拥有最多糖果的孩子
LeetCode 1431 · 简单 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题