思路。样例透露了关键口径：数对按值去重（三个 1 只算一个 1），且 (v, v) 在 \(k = 0\) 时是合法数对。于是把列表转成哈希集合，答案就是集合中满足「\(v + k\) 也在集合里」的值 \(v\) 的个数。每个合法值恰好对应一个数对 \((v, v+k)\)，不重不漏；k 为正时 \(v\) 与 \(v+k\) 地位不同，不会重复计数。

代码。

long long countPairs(const vector<int>& a, int k) {  // 值对 (v, v+k) 同时在数组中出现
    unordered_set<int> s(a.begin(), a.end());
    long long cnt = 0;
    for (int v : s)
        if (s.count(v + k)) ++cnt;             // 每个值只数一次，与「distinct 对」对齐
    return cnt;
}

验证样例：[1,2]、k=1，集合 {1,2}，只有 1 满足 1+1=2 在集合中，输出 1 ✓；[1,1,1,2] 的集合仍为 {1,2}，输出 1 ✓；若 k=0，每个值 v 都满足 v+0=v，输出不同值的个数，与「(1,1)、(2,2)」的口径吻合。

复杂度。时间 \(O(n)\)（哈希均摊），空间 \(O(n)\)。排序 + 双指针亦可（对每个 v 二分查 v+k），\(O(n \log n)\)，不依赖哈希。

边界。k 为负数时（v + k 在集合中）等价于把 k 取绝对值后反向数，结果相同；若面试官改口径为「按下标配对、可重复使用同一元素」，答案变成 \(\sum_v \mathrm{cnt}(v) \cdot \mathrm{cnt}(v+k)\)，需要计数哈希表而非集合——口径变了实现跟着变。

面试怎么讲。先复述样例确认口径（值去重、自身可配对），这是这道题真正的考点；然后一句话给出「哈希集合 + 检查后继」的方案，复杂度顺手报出。

思路。样例说明这是子序列式匹配：SSQHUL 里 S 可取第 1 或第 2 个字符、H 取第 4 个、L 取第 6 个，共 \(2 \times 1 \times 1 = 2\) 种嵌法，与「出现 2 次」吻合。两个层次分开答：存在性/找一次用双指针——文本指针扫描，等于模式当前字符就推进模式指针，模式指针走到头即匹配成功，\(O(n)\)；计数要数出所有嵌法，用 DP：设 \(dp_j\) 为「模式前 \(j\) 个字符的嵌法数」，每读入一个文本字符 c，从大到小更新 \(dp_j \mathrel{+}= dp_{j-1}\)（当 c 等于模式第 j 个字符时）。

怎么读：每个文本字符只能充当模式中的一个位置，倒序更新保证它至多把每个 dp 状态推一步，与 0/1 背包倒序同理。手算 SSQHUL 对 SHL：读 S（第 1 个）后 dp=[1,1,0,0]；再读 S 后 dp=[1,2,0,0]；Q 不动；读 H 后 dp=[1,2,2,0]；读 U 不动；读 L 后 dp=[1,2,2,2]，答案 2 ✓。

代码。

long long countSubsequence(const string& t, const string& p) {  // p 作为子序列在 t 中出现几次
    int m = (int)p.size();
    vector<long long> dp(m + 1, 0);
    dp[0] = 1;                                 // 空模式恰有 1 种匹配方式
    for (char c : t)
        for (int j = m; j >= 1; --j)           // 倒序：一个字符只推进一步
            if (c == p[j - 1]) dp[j] += dp[j - 1];
    return dp[m];
}

复杂度。计数版 \(O(nm)\)（m=3 时即 \(O(3n)\)），空间 \(O(m)\)；双指针存在性版 \(O(n)\)、\(O(1)\) 空间。

边界。模式比文本长时答案为 0；重复字母的计数可能很大（全 S 的文本对 SSS 是组合数级别），必要时取模；若面试官其实想要「连续子串出现次数」，退化为 KMP 或直接暴力滑窗 \(O(nm)\)，先确认是子序列还是子串。

面试怎么讲。用样例算出 2 这个数（体现你读懂了「出现」的定义）是第一得分点；然后分「找一次」与「数全部」两个层次作答，双指针与 DP 各就各位。

思路。本题与 034 章的括号匹配题是近亲，但口径不同：这里只问「最少补几个」，是计数版。单一括号类型时连栈都不需要——用一个计数器扫描：遇左括号加一，遇右括号时若有未配对的左括号则减一，否则答案加一（这个落单的右括号必须在它前面补一个左括号）。扫描结束后计数器剩下的数目，就是还需要补的右括号个数：

两种来源互不抵消：右括号的落单发生在扫描中、左括号的欠账发生在结尾，任何插入都无法一石二鸟，所以直接相加就是下界，且逐个补齐即可达到。

代码。

int minAddToClose(const string& s) {          // 单括号类型：最少补几个括号
    int open = 0, add = 0;
    for (char c : s) {
        if (c == '(') ++open;                  // 多一个待闭合的左括号
        else if (open > 0) --open;             // 就地配对一个
        else ++add;                            // 右括号落单：需要在其前面补 '('
    }
    return add + open;                         // 剩下的 open 每个补一个 ')'
}

例如 "(()(" 扫描后 open=2、add=0，需补 2 个；")(" 得 open=1、add=1，需补 2 个（前面补一个左、末尾补一个右）。

复杂度。时间 \(O(n)\)，空间 \(O(1)\)。

边界。空串返回 0；若括号有多种类型（如 ( [ {），计数器失效，必须用栈——左括号入栈，右括号与栈顶匹配则弹出、否则插入数加一；栈的最终大小也计入。多类型版本的完整实现与「使括号有效的最少添加」一并在 034. 编程四：字符串与栈展开。

面试怎么讲。先声明「单类型退化成计数器，多类型才需要栈」，这个降级判断本身就是考点；再解释两个计数为何直接相加（互不抵消的下界论证）。

思路。用栈模拟真实键入：普通字符入栈，# 时弹栈（空栈则忽略或按题意处理）。两串的栈结果相等即相同。手算样例：a 依次压入 a,b,c，# 弹掉 c，再压 a,b,c，# 弹掉 c，得 "abab"；b 压 a,b,a,b,b，# 弹掉 b，得 "abab"。相同，返回 true。进阶做法是从右往左双指针（跳过被删字符、无额外空间），但 O(n) 空间的栈版本在面试里足够且不易写错。

代码。

bool backspaceCompare(const string& a, const string& b) {
    auto typed = [](const string& s) {         // 栈模拟真实键入结果
        string st;
        for (char c : s) {
            if (c == '#') { if (!st.empty()) st.pop_back(); }
            else st.push_back(c);
        }
        return st;
    };
    return typed(a) == typed(b);
}

复杂度。时间 \(O(n + m)\)，空间 \(O(n + m)\)；反向双指针可做到 \(O(1)\) 空间。

边界。空串与 # 开头（"#a" 等价 "a"）；连续多个 #；栈空时的 # 不产生字符。字符串类的更多栈应用（去重、表达式求值等）在 034 章统一展开。

面试怎么讲。一句话建模：「# 的语义是删除最近未删除的字符，天然是栈」。写完主动提 \(O(1)\) 空间的反向双指针变体，说明你知道空间还能省。

思路。与 032 章的硬币水滴是同一模型：位置 i 的水位为 \(\min(L_i, R_i)\)（左右最高海拔的较小者），存水 \(\min(L_i, R_i) - h_i\)。这里给空间最优的双指针实现：左右两个指针、以及两侧目前见过的最高海拔 lmax 与 rmax。矮的一侧可以先行结算——若 lmax 不超过 rmax，那么左指针处的水位由 lmax 决定（右边一定存在不低于 rmax 从而不低于 lmax 的挡板），与右侧尚未扫描的部分无关；反之结算右侧。每个位置恰好被结算一次。

手算 \([4,2,0,3,2,5]\)：两侧最高夹出的水位依次为 \(4,4,4,4,4,5\)，各列存水 \(0,2,4,1,2,0\)，共 9 单位。

代码。

long long trapWater(const vector<int>& h) {   // 双指针：矮的一侧先结算
    long long water = 0;
    int l = 0, r = (int)h.size() - 1, lmax = 0, rmax = 0;
    while (l < r) {
        lmax = max(lmax, h[l]);
        rmax = max(rmax, h[r]);
        if (lmax <= rmax) water += lmax - h[l++];   // 左侧不更高：水位由 lmax 决定
        else water += rmax - h[r--];
    }
    return water;
}

复杂度。时间 \(O(n)\)，空间 \(O(1)\)；DP 预处理前后缀最值的版本（032 章例题 2）是 \(O(n)\) 空间，还有栈解法按层横向结算，三解法能互相印证。

边界。单调地形不存水；\(n \le 2\) 为 0；首尾两列自身不存水（它们是挡板）。溢出无忧（非负高度，量级有限），但建议仍用 long long 保存累加。

面试怎么讲。先给逐列公式（这决定你有没有建模对），再讲双指针为什么「矮侧先结算」是安全的——这句单调性论证是本题的核心得分点，说不出它，代码就只是背出来的。

简答。先立原假设：若「匹配」是二分类且随机基准为 50%，这是单比例检验（one-proportion z-test）：

显著性完全由样本量 n 决定：n = 100 时 z = −0.6，远未显著；n = 2500 时 z = −3，在 5% 水平下显著差于随机；n = 10000 时 z = −6，铁证显著地差。回答的关键结构是三句话：与什么基准比（50% 还是类别不平衡下的基线）、n 多大（没有 n 就没有显著性）、单侧还是双侧（想证明「有信号」是单侧，想证明「不同于随机」是双侧）。另要主动补一句：若类别不平衡，「随机也能蒙对」的比例不是 50%，先算基线再谈显著；统计显著也不等于经济显著。019. 概率六：假设检验与置信区间有检验框架的完整展开。

简答。第一层：MSE 相近是在同一样本上算的，直接比较会低估两者的真实差异——用交叉验证（cross-validation）或时序上的滚动窗口（rolling origin）得到多个折上的误差，再看两者差的分布。第二层：若两个变量是对同一目标的两组预测，对损失差 \(d_t = e_{1t}^2 - e_{2t}^2\) 做 Diebold–Mariano 检验，原假设 \(E[d_t] = 0\)，t 统计量用 Newey–West 修正自相关——这是预测比较的标准工具。第三层：相近的 MSE 可能来自完全不同的偏差—方差组合（一个高偏差低方差、一个低偏差高方差），按子区间、按状态分解残差能看出谁在什么场景崩。收尾一句：统计上分不出优劣时，选更稳健、更可解释的那个。检验细节链接 019 章，偏差—方差分解见 027. 统计二：岭回归、Lasso 与模型选择。

简答。归并排序：分治递归、稳定、任何输入都 \(O(n \log n)\)，代价是 \(O(n)\) 辅助数组。快速排序：原地、缓存友好，平均 \(O(n \log n)\)、最坏 \(O(n^2)\)（已排序输入配固定基准），随机化基准或三数取中把最坏情形变成小概率事件。稳定性与「快排为什么实践中更快」的讨论见 007. 排序算法：稳定性、归并、快排与堆排。

简答。面向对象编程（object-oriented programming, OOP）把数据与操作它的函数捆绑成对象，四大支柱：封装（encapsulation，隐藏内部状态、只暴露接口）、继承（inheritance，复用与特化）、多态（polymorphism，同一接口不同实现）与抽象（abstraction，只暴露必要行为）。项目例子的标准讲法是回测框架：Instrument 与 Position 封装各自的字段不变量，Strategy 作为抽象基类只规定 onBar 接口，均值回归、动量等具体策略派生实现多态；新增策略不需要改动回测引擎——「对扩展开放、对修改关闭」这句话说出来，比罗列定义有力得多。最小示意：

class Strategy {                        // 抽象基类：接口即契约
public:
    virtual ~Strategy() = default;
    virtual void onBar(double price) = 0;   // 多态入口：每根 K 线回调
};

class MeanReversion : public Strategy {    // 具体策略只关心自己的逻辑
    double fair;
public:
    explicit MeanReversion(double f) : fair(f) {}
    void onBar(double price) override { /* 偏离 fair 超阈值就调仓 */ }
};

简答。由对称性 E[x] 等于球心横坐标。方差用球面方程：\(x, y, z\) 同分布，故 \(r^2 = x^2 + y^2 + z^2\) 取期望得 \(3\,E[x^2] = r^2\)，于是 \(\mathrm{Var}(x) = E[x^2] - (E[x])^2 = \tfrac{r^2}{3}\)；单位球上即 \(\tfrac13\)。这道题的完整对称性论证在 020. 概率七：条件概率与对称性。

简答。指示变量（indicator）加期望线性：16 个相邻位置，每个位置是异性对的概率为 \(2 \cdot \tfrac{8}{17} \cdot \tfrac{9}{16} = \tfrac{9}{17}\)，故期望为 \(16 \cdot \tfrac{9}{17} = \tfrac{144}{17} \approx 8.47\)。指示变量法的系统训练见 021. 概率八：期望计算进阶。