建模。第一问是逐位归一化比较；第二问是「增删型编辑距离至多为一」的判定。两者共用同一个小写折叠函数。

思路。第一问：长度不等直接假，否则逐位比较小写化结果。第二问：先做长度闸门——两串等长时一次增删必然改变长度、不可能保持相等，直接退回第一问的精确比较（如 b 与 c 为假）；长度差恰为 1 时双指针前进，首次失配时从较长串跳过一个字符并记下「已用机会」，第二次失配立即返回假；循环结束后尾部剩余字符总数不超过一即为真。整段算法只扫描每个字符一次。

// 第一问：忽略大小写比较两个字符串是否相同
bool sameIgnoreCase(const string& a, const string& b) {
    if (a.size() != b.size()) return false;              // 长度不同必不相等
    for (size_t i = 0; i < a.size(); ++i)
        if (tolower((unsigned char)a[i]) != tolower((unsigned char)b[i]))
            return false;                                // 逐位小写化后比较
    return true;
}

// 第二问：忽略大小写后，至多增/删一个字符仍相等
bool sameOrOneEdit(const string& a, const string& b) {
    int n = a.size(), m = b.size();
    if (abs(n - m) > 1) return false;                   // 长度差超过 1 直接排除
    if (n == m) return sameIgnoreCase(a, b);            // 等长：一次增删必改变长度
    int i = 0, j = 0;
    bool skipped = false;                                // 是否用过一次跳过机会
    while (i < n && j < m) {
        if (tolower((unsigned char)a[i]) == tolower((unsigned char)b[j])) {
            ++i; ++j;                                    // 匹配：双指针同步前进
        } else {
            if (skipped) return false;                   // 第二次失配必不相等
            skipped = true;
            if (n >= m) ++i; else ++j;                  // 跳过较长串的一个字符
        }
    }
    return (n - i) + (m - j) <= 1;                      // 尾部至多剩一个字符
}

复杂度。时间 \(O(n+m)\)，空间 \(O(1)\)，没有任何额外结构。

边界。空串对空串为真；空串对单字符为真（一次插入）；等长串（如 b 与 c）一次增删后长度必然不等，除原本相同外都为假——这正是等长分支直接退回精确比较的原因。若考官改口径为「恰好编辑一次」，等长直接返回假（原本相同是零次编辑），长度差 1 时要求「恰用一次跳过」或「尾部恰剩一个」二者恰居其一。若再允许「替换一个字符」，算法骨架不变：等长串失配时改为 \(i, j\) 同时前进（再失配即假）。非 ASCII 字节要转 unsigned char 后再折叠，这是 C/C++ 的经典陷阱。

面试怎么讲。先把「归一化 + 长度闸门 + 一次跳过」三步说出口，再补一句不变量：「失配前两串前缀逐位相等，失配点唯一，所以跳较长串一个字符就完成对齐验证」——这句话比代码更能证明你理解算法。

建模。每个元素面对「选/不选」的二叉决策，\(n\) 个元素共 \(2^n\) 个子集。两种枚举姿势对应两棵同构的树：位掩码把树压成一层循环，回溯显式展开树的路径。

解法一：位掩码。整数 \(\text{mask} \in [0, 2^n)\) 与子集一一对应，第 \(i\) 位为 1 表示选入第 \(i\) 个元素：

// 解法一：位掩码枚举，每个 mask 对应一个子集
vector<vector<int>> subsets(const vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> res;
    for (int mask = 0; mask < (1 << n); ++mask) {       // 枚举全部 2^n 个掩码
        vector<int> cur;
        for (int i = 0; i < n; ++i)
            if (mask >> i & 1) cur.push_back(nums[i]); // 第 i 位为 1 则选入
        res.push_back(move(cur));
    }
    return res;
}

解法二：回溯。在第 \(i\) 层决定是否选入 \(\text{nums}[i]\)，走到叶子收集一个子集：

// 解法二：回溯，每层决定「选/不选」当前元素
void dfs(int idx, vector<int>& cur, vector<vector<int>>& res,
         const vector<int>& nums) {
    if (idx == (int)nums.size()) { res.push_back(cur); return; } // 叶子：收集子集
    dfs(idx + 1, cur, res, nums);                       // 分支一：不选 nums[idx]
    cur.push_back(nums[idx]);
    dfs(idx + 1, cur, res, nums);                       // 分支二：选 nums[idx]
    cur.pop_back();                                     // 撤销选择，回溯
}

复杂度。两种解法都是时间 \(O(n \cdot 2^n)\)（每个子集要 \(O(n)\) 复制）、输出本身就有这个规模，已是最优；空间不计输出为 \(O(n)\) 递归栈。

边界。空数组返回仅含空集的 \(\{\{\}\}\)；\(n\) 超过 25 左右时 \(2^n\) 已不可枚举，应向考官说明并确认数据范围。若元素可能重复（题面变体），先排序，回溯时同层跳过相同值即可去重——位掩码版没有这么好改，这是回溯版的存在价值。

面试怎么讲。先说「幂集大小 \(2^n\)，所以任何算法都至少这个量级」，把下界交代清楚；再讲两种实现的取舍：掩码版短、适合无重复输入，回溯版可扩展到去重与剪枝（如只枚举大小为 \(k\) 的子集）。

思路。维护 \(r\)：以当前元素为右端点、公差延续时「新增」的等差子数组个数。右端点每右移一位且公差延续，新增数恰为上一位置新增数加一；公差断裂则清零。答案为所有新增数之和，这正是知识点二里的延展计数公式的增量形式。

int countArithmeticSlices(vector<int>& a) {
    int n = a.size(), ans = 0, run = 0;                  // run：以 i 结尾新增的子数组数
    for (int i = 2; i < n; ++i) {
        if (a[i] - a[i-1] == a[i-1] - a[i-2])           // 公差延续
            ans += ++run;
        else
            run = 0;                                     // 公差断裂，重新起算
    }
    return ans;                                          // 长度小于 3 自然返回 0
}

数值结果。\([1,2,3,4]\) 得 3（子数组 \([1,2,3]\)、\([2,3,4]\)、\([1,2,3,4]\)）；\([1,3,5,7,9]\) 得 6，与公式 \(\frac{(5-1)(5-2)}{2}=6\) 一致。

复杂度与边界。时间 \(O(n)\)、空间 \(O(1)\)。数组长度小于 3 返回 0；公差可以是 0（如 \([5,5,5]\) 计 1）也可以是负数；若 int 差值可能溢出（元素接近 INT 边界），用 long long 存差。若考官追问「等差子序列」（非连续），那是另一道 \(O(n^2)\) DP 题，用「公差到以该元素结尾的个数」做状态。

面试怎么讲。先在小例子上数一遍「以每个右端点新增几个」，让考官看到增量计数的过程，再给出代码与公式两条互相印证的路径。

思路。单指针扫描，\(\text{cur}\) 记录以当前元素结尾的递增段长度：\(\text{cur} = \text{cur}+1\) 若 \(a[i] \gt a[i-1]\)，否则重置为 1。这是「断点重置」的最小样例。

int longestStrictlyIncreasing(vector<int>& a) {
    int best = 0, cur = 0;
    for (size_t i = 0; i < a.size(); ++i) {
        cur = (i > 0 && a[i] > a[i-1]) ? cur + 1 : 1;   // 断裂处重置为 1
        best = max(best, cur);
    }
    return best;                                         // 空数组返回 0
}

数值结果。\([1,3,5,2,4,6]\) 中 \([1,3,5]\) 与 \([2,4,6]\) 各长 3，答案 3。

复杂度与边界。时间 \(O(n)\)、空间 \(O(1)\)。空数组返回 0，单元素返回 1；「严格」二字去掉后条件改 \(a[i] \ge a[i-1]\)（用 \(\gt\) 判断改 \(>=\)）。面试时主动指出：若考官问的是子序列版本，复杂度跳到 \(O(n\log n)\)，切勿混答。

建模。子列保持原相对顺序，选中元素的运行和每一步都不得为负——等价于「血量永不为负地尽量多喝药水」的经典模型。目标是最大化选中个数。

思路（贪心 + 小根堆）。从左到右把每个元素都先选入：累加进运行和、压入小根堆。一旦运行和为负，撤销堆中最小的元素（把它从和里减掉、出堆）。撤销一个更早的元素只会抬高其后所有前缀和，不破坏已有约束；交换论证说明若存在更长的可行子列，其中的最差选择总能与被撤销者交换得到不劣解，故贪心得到最大长度。

int longestNonnegPrefix(vector<int>& a) {
    priority_queue<int, vector<int>, greater<int>> pq;   // 小根堆：缓存已选元素
    long long sum = 0;                                   // 已选元素之和（防溢出）
    for (int x : a) {
        sum += x;
        pq.push(x);
        if (sum < 0) { sum -= pq.top(); pq.pop(); }     // 撤掉最负者，抬高后缀
    }
    return (int)pq.size();
}

数值结果。\([3,-3,5,-2,-2,-2,-2,6,-1]\)：扫描到第三个 \(-2\)（数组第 6 个元素）时运行和为 \(-1\)，撤销最负的 \(-3\)，运行和回到 \(2\)；此后一路不再越界，最终选中 \(\{3,5,-2,-2,-2,-2,6,-1\}\)，按原顺序前缀和为 \(3,8,6,4,2,0,6,5\)，全部非负，长度 8。全取 9 个元素不可行（前缀和在第三个 \(-2\) 处为 \(-1\)），故 8 即最优。

复杂度与边界。均摊时间 \(O(n \log n)\)、空间 \(O(n)\)。全负数组时堆会不断撤销到只剩一个最大元素（其前缀和可能为负则继续撤到空，长度 0——按题意空子列前缀和无违规，返回 0 或 1 需与考官确认口径）。常见错误方向是「从右往左贪心先取大数」，在保持原顺序的版本里不成立，因为约束作用在从左数起的每一步前缀和上。

面试怎么讲。点明这是「前缀约束下的最大选择」模型，先说暴力 \(O(2^n)\)，再引出撤销最差选择的贪心与交换论证，最后补复杂度。

建模。先澄清口径：设全局众数为 \(M\)、全局频率 \(f\)。「以相同频率出现且仍支配」的子数组必须包含 \(M\) 的全部 \(f\) 次出现，因此最短子数组就是从 \(M\) 的第一次出现到最后一次出现的窗口，答案为 \(\text{last} - \text{first} + 1\)。

int smallestDominatingWindow(vector<int>& a) {
    if (a.empty()) return 0;                             // 空数组特判
    unordered_map<int, int> freq;
    int modeCnt = 0;
    for (int x : a) modeCnt = max(modeCnt, ++freq[x]);   // 全局最大出现次数
    int M = a[0];
    for (int x : a) if (freq[x] == modeCnt) { M = x; break; } // 任取一个众数
    int first = -1, last = -1;
    for (int i = 0; i < (int)a.size(); ++i)              // 记录 M 的首末出现位置
        if (a[i] == M) { if (first < 0) first = i; last = i; }
    return last - first + 1;                             // 覆盖全部出现的最短窗口
}

数值结果。\([1,1,3,2,4,2,7,8]\)：1 与 2 并列频率 2。取 \(M=1\)，窗口 \([1,1]\) 长 2；取 \(M=2\)，它首次出现在下标 3、最后一次在下标 5，窗口 \([2,4,2]\) 长 3——并列时应对每个候选分别计算再取最小，本例答案 2。上面的实现取「扫到的第一个众数」，本例恰好就是最短者；若要求任意输入下都返回最短，需对每个达到最高频次的值各算一次窗口再取最小。

复杂度与边界。时间 \(O(n)\)、空间 \(O(n)\)。并列众数如上分别计算；若考官改口径为「\(M\) 只需在子数组内仍是众数（频率可小于全局 \(f\)）」，答案退化为 1（单元素子数组 \([M]\)），此时应补充「长度不小于某阈值」等限制才有意义——把口径问清比解题本身更重要。

题意。求\(\max_{i\lt j}(a_j-a_i)\)，若不存在严格正差返回−1。PDF的“not ascending at any place”按“没有任何上升机会”解释；不能翻译成“任意一处下降就不合法”。如果面试官另行要求整个数组非降，那是额外限制的另一版本。

不变量。扫描到j之前，minimum是\(a_0,\ldots,a_{j-1}\)的最小值。以j作右端的最好差就是\(a_j-\mathrm{minimum}\)，再更新全局答案和minimum。必须先比较再纳入当前元素，保证两个下标不同。

long long maxPositiveDiff(const vector<long long>& a) {
    if (a.size() < 2) return -1;
    long long minimum = a.front(), answer = -1;
    for (size_t j = 1; j < a.size(); ++j) {
        if (a[j] > minimum) answer = max(answer, a[j] - minimum);
        minimum = min(minimum, a[j]);  // Update after comparing, so i < j.
    }
    return answer;
}

[1,3,2]返回2；[7,1,5,3,6,4]返回5；[3,2,1]、[2,2]和单元素均返回−1。O(n)时间、O(1)空间；假定两元素之差可用long long表示，覆盖int输入及常见面试规模。全相等时不存在正差，不能返回0。

原题的计数对象。PDF写“pairs of values”，并用(a,b)与(c,d)的数值是否相同区分，因此主解按值去重。原数组[1,1,3,2,4,2,7,8]、k=2只有(1,3)与(2,4)，答案2。先存频数，对每个不同值v只检查一次v+k即可，重复下标不增加值对。

k=0还要问是否允许自配。C14明确允许(1,1)只用同一个1；C51没有重述这一点。allowSelf=true沿用C14口径，每个不同值贡献一个；false要求至少出现两次，仍只贡献一个值对。下标对是另一输出：k≠0时乘两类频数，k=0时按两个不同下标、无序组合数c(c−1)/2计，不能称为有序对。

long long countValuePairs(const vector<int>& a, int k, bool allowSelf = true) {
    unordered_map<long long, int> frequency;
    for (int x : a) ++frequency[x];
    long long answer = 0;
    for (const auto& [value, count] : frequency) {
        if (k == 0) answer += allowSelf || count >= 2;
        else if (frequency.count(value + (long long)k)) ++answer;
    }
    return answer;
}

long long countIndexPairs(const vector<int>& a, int k) {
    unordered_map<long long, long long> frequency;
    for (int x : a) ++frequency[x];
    long long answer = 0;
    for (const auto& [value, count] : frequency) {
        if (k == 0) answer += count * (count - 1) / 2;
        else if (frequency.count(value + (long long)k)) answer += count * frequency.at(value + k);
    }
    return answer;
}

两个函数对原数组、k=2分别返回2与4，名称明确区分对象。k可为负，值v+k保留方向；非零k下每对恰计一次。平均O(n)时间、O(n)空间，键用long long避免int极值加k溢出。

思路。前缀和加哈希的标准应用（与 033 章「和为 k 的子数组」同题，此处给实现备查）：记前缀和 \(\text{pre}\)，子数组 \((i, j]\) 的和为 \(k\) 等价于 \(\text{pre}_j - \text{pre}_i = k\)；扫描时查询哈希表中 \(\text{pre}-k\) 的出现次数并累加，再把当前 \(\text{pre}\) 计入。

int subarraysSumK(const vector<int>& a, int k) {
    unordered_map<long long, int> cnt{{0, 1}};            // 前缀和 0 已出现一次
    long long pre = 0;
    int ans = 0;
    for (int x : a) {
        pre += x;                                        // 当前前缀和
        if (cnt.count(pre - k)) ans += cnt[pre - k];     // 此前有多少个相等前缀和
        ++cnt[pre];
    }
    return ans;
}

数值结果。\([1,1,1]\)、\(k=2\) 得 2（两个 \([1,1]\)）。

复杂度与边界。时间 \(O(n)\)、空间 \(O(n)\)。负数元素存在时滑动窗口失效，必须用前缀和；前缀和存 long long 防溢出；初始 \(\{0:1\}\) 不能忘，否则所有从下标 0 出发的子数组都会漏计。

完整保留两种证据。PDF原句在“频率、值”后写“in ascending order”，可以读成两者升序；但给出的例子是[3,5,2,2,4]→[2,2,3,4,5]，并解释“2出现两次，所以排在前面”，明确对应频率降序、同频值升序。这两种规则冲突，不能悄悄改掉原示例。

实现按参数分流。默认frequencyDescending=true跟随PDF示例，得到[2,2,3,4,5]；传false按频率升序得到[3,4,5,2,2]。两种模式的同频次序均按数值升序。

vector<int> freqSort(vector<int> a, bool frequencyDescending = true) {
    unordered_map<int, int> count;
    for (int x : a) ++count[x];
    sort(a.begin(), a.end(), [&](int x, int y) {
        if (count[x] != count[y])
            return frequencyDescending ? count[x] > count[y] : count[x] < count[y];
        return x < y;
    });
    return a;
}

先用哈希计频，再自定义比较器，时间O(n log n)、空间O(n)。空表原样返回；比较器只读取已存在的频数，不在排序时改变频数。若改成同频按首次出现位置，必须另外记录该位置，不能继续用x<y。