LeetCode 题解工作台
得到子序列的最少操作次数
给你一个数组 target ，包含若干 互不相同 的整数，以及另一个整数数组 arr ， arr 可能 包含重复元素。 每一次操作中，你可以在 arr 的任意位置插入任一整数。比方说，如果 arr = [1,4,1,2] ，那么你可以在中间添加 3 得到 [1,4, 3 ,1,2] 。你可以在数组最…
4
题型
5
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
根据题意，`target` 和 `arr` 这两个数组的公共子序列越长，需要添加的元素就越少。因此，最少添加的元素个数等于 `target` 的长度减去 `target` 和 `arr` 的最长公共子序列的长度。 但是，[求最长公共子序列](https://github.com/doocs/leetcode/blob/main/solution/1100-1199/1143.Longest%20C…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个数组 target ，包含若干 互不相同 的整数，以及另一个整数数组 arr ，arr 可能 包含重复元素。
每一次操作中，你可以在 arr 的任意位置插入任一整数。比方说，如果 arr = [1,4,1,2] ，那么你可以在中间添加 3 得到 [1,4,3,1,2] 。你可以在数组最开始或最后面添加整数。
请你返回 最少 操作次数，使得 target 成为 arr 的一个子序列。
一个数组的 子序列 指的是删除原数组的某些元素（可能一个元素都不删除），同时不改变其余元素的相对顺序得到的数组。比方说，[2,7,4] 是 [4,2,3,7,2,1,4] 的子序列（加粗元素），但 [2,4,2] 不是子序列。
示例 1：
输入：target = [5,1,3], arr = [9,4,2,3,4]
输出：2
解释：你可以添加 5 和 1 ，使得 arr 变为 [5,9,4,1,2,3,4] ，target 为 arr 的子序列。
示例 2：
输入：target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]
输出：3
提示：
1 <= target.length, arr.length <= 1051 <= target[i], arr[i] <= 109target不包含任何重复元素。
解题思路
方法一：最长递增子序列 + 树状数组
根据题意，target 和 arr 这两个数组的公共子序列越长，需要添加的元素就越少。因此，最少添加的元素个数等于 target 的长度减去 target 和 arr 的最长公共子序列的长度。
但是，求最长公共子序列的时间复杂度为 ，无法通过本题，需要转变思路。
我们可以用一个哈希表记录 target 数组中每个元素的下标，然后遍历 arr 数组，对于 arr 数组中的每个元素，如果哈希表中存在该元素，则将该元素的下标加入到一个数组中，这样就得到了一个新的数组 nums，该数组是 arr 中的元素在 target 数组中的下标（去掉了不在 target 中的元素），该数组的最长递增子序列的长度就是 target 和 arr 的最长公共子序列的长度。
因此，问题转化为求 nums 数组的最长递增子序列的长度。参考 300. 最长递增子序列。
时间复杂度 ，空间复杂度 。其中 和 分别为 target 和 arr 的长度。
class BinaryIndexedTree:
__slots__ = "n", "c"
def __init__(self, n: int):
self.n = n
self.c = [0] * (n + 1)
def update(self, x: int, v: int):
while x <= self.n:
self.c[x] = max(self.c[x], v)
x += x & -x
def query(self, x: int) -> int:
res = 0
while x:
res = max(res, self.c[x])
x -= x & -x
return res
class Solution:
def minOperations(self, target: List[int], arr: List[int]) -> int:
d = {x: i for i, x in enumerate(target, 1)}
nums = [d[x] for x in arr if x in d]
m = len(target)
tree = BinaryIndexedTree(m)
ans = 0
for x in nums:
v = tree.query(x - 1) + 1
ans = max(ans, v)
tree.update(x, v)
return len(target) - ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n log n) using binary search for LIS computation, where n is arr.length. Space complexity is O(m) for the hash map, where m is target.length. These bounds reflect the pattern of mapping target to arr indices and maintaining increasing sequences efficiently. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expecting hash map usage for index lookup rather than naive scanning.
- question_mark
Look for LIS or patience sorting approach on mapped indices.
- question_mark
Clarify edge cases where arr has duplicates or missing elements from target.
常见陷阱
外企场景- error
Forgetting to handle elements in arr that are not in target, which should be skipped.
- error
Using naive O(n*m) LCS instead of LIS-based optimization on indices.
- error
Miscounting insertions when LIS covers only a partial subsequence of target.
进阶变体
外企场景- arrow_right_alt
Compute minimum deletions in arr to match target subsequence.
- arrow_right_alt
Find minimal operations when both insertion and deletion are allowed.
- arrow_right_alt
Handle repeated elements in target instead of assuming distinct values.