O(1) 插入删除随机：哈希定位，交换再删
数组负责按下标取和弹尾，哈希负责按值找下标。中间元素要删时，先和末尾交换，再弹出，避免 O(n) 搬移。
nums 存值，pos 存值到下标。插入：已存在返回假，否则 append 并登记新下标。删除：用 pos 找到 i，与末尾交换，把被换上来的值的下标改成 i，再截掉尾巴并 delete pos[val]。随机：rand.Intn(len) 直接读。均摊 O(1)，空间 O(n)。
这是 LeetCode 380. Insert Delete GetRandom O(1)。大白话：实现 RandomizedSet，三种操作平均都要 O(1)。insert(val) 不存在才插入，返回是否成功；remove(val) 存在才删除，返回是否成功；getRandom 在当前集合里等概率返回一个元素。元素不重复。
只拿哈希表：插入删除 O(1)，但哈希表没有下标，做不到等概率随机，遍历再取是 O(n)。只拿动态数组：随机和尾插 O(1)，按值删除要先找再搬，O(n)。缺口是两套结构互相补上对方不能做的那一句。
主例演示删除：当前数组 [2, 1, 3, 5]，要删 1。1 在下标 1，末尾是 5；交换后变成 [2, 5, 3, 1]，弹出 1，留下 [2, 5, 3]，并把 5 的下标改成 1。
三种操作卡在两种结构的短板上
insert 要判重。哈希表按值查询 O(1)，数组按值扫描 O(n)。getRandom 要等概率。数组按下标读 O(1)，哈希表的迭代顺序不是均匀随机。remove 要按值删。哈希表能找到，数组删中间要把后面的元素全部左移，O(n)。
单独用哪一种，都会有一个操作掉到线性。题目要的不是「三个操作都能做」，而是「三个都是平均 O(1)」。必须让数组和哈希表同时在场，并且想办法把数组删除中间元素的搬移去掉。
数组存值，哈希存下标
nums 是元素的密集排列，下标 0 到 len−1 都有值，getRandom 才能 rand.Intn(len) 一下命中。pos[val] = i 表示 val 现在躺在 nums[i]。两份数据必须同步：nums[i] = v 当且仅当 pos[v] = i。
插入 val：先查 pos，在就返回 false。不在则 append 到 nums 尾，pos[val] = 新长度减一。尾插均摊 O(1)，不必移动别人。删除的麻烦留到下一节：中间那个洞不能真的留着，否则随机会抽到空洞，下标也不再密集。
分工数组回答「第 i 个是谁」，哈希回答「这个值在第几格」。删的时候两句都要改，漏改哈希，下次按值就找到错位置。
删除：和末尾交换，弹出，改被换上来的下标
数组不允许中间留洞，又不想 O(n) 左移。题目不要求保持插入顺序，于是把待删位置和最后一个位置交换，再把长度减一。被删的值现在在尾巴上，弹出是 O(1)；原来的末尾元素搬到了空洞里，数组重新变密集。
交换之后必须改哈希：被换上来的那个值，下标已经不是原来的 last，而是 i。漏掉这一句，以后再删它会走到旧下标。待删值自己的 pos 记录最后 delete 掉。删的正好是末尾元素时，交换是自己和自己，仍然走同一套，不要单独分支漏掉 delete。
用手走主例。nums=[2,1,3,5]，pos：2→0、1→1、3→2、5→3。删 1，i=1。演示第一帧高亮下标 1。与 last=3 交换，数组变成 [2,5,3,1]，pos[5] 改成 1，1 暂时在下标 3。演示第二帧。截掉尾巴，delete pos[1]，留下 [2,5,3]。演示第三帧删除完成。之后 getRandom 只在 0、1、2 三个下标里抽。
随机：密集下标上抽一个整数
getRandom 就是 nums[rand.Intn(len(nums))]。能 O(1) 是因为删除始终保持数组无洞。题目保证调用时集合非空，不必在空数组上取模。
等概率来自「每个值恰好占一格」。若删除只在哈希表里抹掉、数组里留着旧值，随机会抽到已删元素，也会让还活着的元素概率不均。交换删除不是技巧，是为了保住这一格一值。
十二行 Go：数组 + 哈希
type RandomizedSet struct {nums []intpos map[int]int}func (r *RandomizedSet) Remove(val int) bool {i, ok := r.pos[val]; if !ok { return false }last := len(r.nums) - 1r.nums[i], r.nums[last] = r.nums[last], r.nums[i]r.pos[r.nums[i]] = ir.nums = r.nums[:last]delete(r.pos, val)return true}
1pos 找不到 val 就返回 false。主例删 1 时 i=1。
2与 last 交换。主例 1 和 5 换位，数组变成 [2,5,3,1]。
3r.pos[r.nums[i]] = i 改的是被换上来的 5，不是 1。漏掉这行，5 的下标仍停在 3。
4截断尾巴再 delete pos[val]。两步都要做：数组去掉 1，表也去掉 1。
5删末尾元素时交换是空操作，仍然靠最后两行收尾。
总结
数组给随机，哈希给定位；删除和末尾交换再弹。主例删 1，5 补到下标 1。
- 单用数组或单用哈希，都会有一个操作掉到 O(n)。缺口是两套结构同步。
- 交换删除牺牲顺序，换来中间删除 O(1)。必须更新被换上来的值的下标。
- 随机建立在「一值一格、没有空洞」上。删完不截尾巴，概率就坏了。