本文详解 leetcode 1389 题「创建目标数组」的正确解法：根据索引数组 `index` 中指定的位置，将 `nums` 中的元素逐个插入到动态增长的目标数组中，关键在于使用 `arraylist.add(int index, e element)` 实现 o(1) 平均复杂度的中间插入。
原题要求：给定整数数组 nums 和索引数组 index，需按顺序将 nums[i] 插入到目标数组的 index[i] 位置（即插入后该元素位于第 index[i] 个索引处，0 起始）。注意——这不是简单赋值，而是动态插入：后续插入会自动将已有元素向右推移。
你最初的实现存在两个根本性错误：
- 使用固定长度数组 int[] target = new int[nums.length]，无法支持中间插入（只能覆盖，不能平移）；
- 内层循环 for (int j = 0; j
✅ 正确思路是借助动态扩容的 List（如 ArrayList），其 add(int index, E element) 方法天然支持在任意有效索引处插入，自动处理元素位移。插入完成后，再通过 Stream 转为原始 int[] 数组。
以下是完整可运行的解决方案：
import java.util.*;
public class LeetCode1389 {
public static void main(String[] args) {
System.out.println(Arrays.toString(createTargetArray(new int[]{0,1,2,3,4}, new int[]{0,1,2,2,1})));
// 输出: [0, 4, 1, 3, 2]
// 解释:
// i=0: nums[0]=0, index[0]=0 → [] → [0]
// i=1: nums[1]=1, index[1]=1 → [0] → [0,1]
// i=2: nums[2]=2, index[2]=2 → [0,1] → [0,1,2]
// i=3: nums[3]=3, index[3]=2 → [0,1,2] → [0,1,3,2]
// i=4: nums[4]=4, index[4]=1 → [0,1,3,2] → [0,4,1,3,2]
}
static int[] createTargetArray(int[] nums, int[] index) {
List target = new ArrayList<>(nums.length);
for (int i = 0; i < nums.length; i++) {
target.add(index[i], nums[i]); // 在 index[i] 处插入 nums[i]
}
return target.stream().mapToInt(Integer::intValue).toArray();
}
} ? 关键点说明：
- ArrayList.add(index, element) 时间复杂度平均为 O(n)，但这是本题最优解——因为题目明确要求“插入到指定位置”，而数组无法高效支持此操作；
- 初始化 new ArrayList(nums.length) 是良好实践，可避免多次扩容，提升性能；
- mapToInt(Integer::intValue) 比 i -> i 更语义清晰，显式表明装箱/拆箱意图；
- 无需手动校验 index[i] 是否越界——题目已保证所有插入操作合法（0 ≤ index[i] ≤ target.size()）。
⚠️ 注意事项：
- 切勿尝试用 int[] 手动模拟插入（需频繁 System.arraycopy），代码冗长且易错；
- 若追求极致性能（如海量数据），可考虑预分配 int[] + 双指针移动，但本题场景下 ArrayList 方案简洁、健壮、符合工程实践。
总结：面对“按序插入至指定位置”类问题，优先选择支持动态索引插入的集合类型（如 ArrayList），而非硬套静态数组，这是理解抽象数据结构优势的关键一步。
