Day 8。
今天两道题，一个是 3Sum 系列的延伸，一个是经典的电话号码字母组合。
一题偏 排序 + 双指针优化，一题偏 组合生成。

今天的关键词：最接近、双指针、笛卡尔积、迭代构造。

🧠 LeetCode 16 – 3Sum Closest

💡 思路总结

这题和昨天的 3Sum 很像，但目标变了：

  • 昨天是找 和等于 0 的所有三元组
  • 今天是找 最接近 target 的三数之和

所以思路仍然是经典套路：

  1. 先排序
  2. 固定一个数
  3. 剩下两个数用双指针逼近

💻 代码实现

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int min_diff = INT_MAX;
        int result = 0;

        int limit = nums.size();
        sort(nums.begin(), nums.end());

        for (int i = 0; i < limit - 2; i++) {
            int left = i + 1;
            int right = limit - 1;

            while (right > left) {
                int sum = nums[i] + nums[left] + nums[right];

                if (abs(sum - target) < min_diff) {
                    min_diff = abs(sum - target);
                    result = sum;
                }

                if (sum == target) {
                    return sum;
                }
                else if (sum < target) {
                    left++;
                }
                else {
                    right--;
                }
            }
        }

        return result;
    }
};

📌 知识点总结

1️⃣ 和 3Sum 的联系

这题其实就是在昨天 3Sum 的框架上稍微改了一下目标：

  • 不再要求恰好等于某个值
  • 而是要求“距离 target 最近”

所以本质框架没变，仍然是：

排序 + 固定一个数 + 双指针

这说明很多题并不是全新的，而是在旧模板上做变化。

2️⃣ 为什么双指针仍然成立

排序后，如果当前：

  • sum < target，说明和偏小，需要更大的值，所以 left++
  • sum > target，说明和偏大，需要更小的值，所以 right--

这个移动逻辑和昨天一模一样。

3️⃣ 用 min_diff 记录最优答案

你这里用了：

if (abs(sum - target) < min_diff) {
    min_diff = abs(sum - target);
    result = sum;
}

这是这题最核心的一步。
不需要存所有答案，只要维护当前最优即可。

这种“维护最优值”的思想在很多题里都特别常见。

4️⃣ 提前返回

if (sum == target) {
    return sum;
}

这个写得很好。
因为已经完全等于 target 了，不可能再有更接近的结果，直接返回就是最优解。

☎️ LeetCode 17 – Letter Combinations of a Phone Number

💡 思路总结

这题要求根据数字字符串，返回所有可能的字母组合。

比如：

  • 2 -> abc
  • 3 -> def

如果输入 "23"，那就要把：

  • "abc"
  • "def"

做组合，得到：

ad, ae, af, bd, be, bf, cd, ce, cf

你的做法很巧妙，用的是 迭代扩展 的思路：

  • 初始结果设为 [""]
  • 每读一个数字，就把当前结果和这个数字对应的字符集做拼接
  • 一轮一轮扩展下去

💻 代码实现

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};

        vector<string> mapping = {
            "abc", "def", "ghi", "jkl",
            "mno", "pqrs", "tuv", "wxyz"
        };

        vector<string> result = {""};

        for (char d : digits) {
            vector<string> temp;
            string letters = mapping[d - '2'];

            for (string s : result) {
                for (char c : letters) {
                    temp.push_back(s + c);
                }
            }

            result = temp;
        }

        return result;
    }
};

📌 知识点总结

1️⃣ 映射关系

先建立数字到字母的映射：

2 -> "abc"
3 -> "def"
4 -> "ghi"
...

这里用 mapping[d - '2'] 非常简洁。

比如：

  • '2' - '2' = 0
  • '3' - '2' = 1

正好对应下标。

2️⃣ 组合生成的本质

这题本质上是在不断做“拼接扩展”。

比如初始：

result = [""]

处理数字 2：

["a", "b", "c"]

再处理数字 3：

["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

也就是说：

旧结果集 × 新字符集 = 新结果集

这其实就是一个很典型的笛卡尔积思想。

3️⃣ 迭代法很清晰

很多人做这题会想到回溯，当然也能做。
但你现在这版用迭代法，逻辑也非常清楚：

  • 当前已有若干前缀
  • 每来一个新数字，就把所有前缀统一扩展一遍

这说明你已经开始能从不同角度理解题目了，不只是死套一种模板。

4️⃣ 空字符串边界处理

if (digits.empty()) return {};

这个判断非常必要。
因为如果输入为空，就没有任何组合，直接返回空数组即可。

🧩 今日总结

题目核心思想
LeetCode 16排序 + 双指针 + 维护最优解
LeetCode 17映射 + 组合扩展 + 迭代构造

今天这两题虽然类型不同，但都很有代表性：

  • 一题让你继续巩固 3Sum 系列模板
  • 一题让你开始接触“组合类问题”的构造方式

🧠 今日收获

今天最值得记住的两个模型：

1. 最优解维护型题目

如果题目不是问“有没有”，也不是问“全部答案”，而是问：

  • 最大
  • 最小
  • 最接近
  • 最优

那往往就要想到：

遍历过程中维护当前最优值

这题的 min_diff 就是这个思路。

2. 组合生成型题目

这类题经常有两种做法：

  • 回溯
  • 迭代扩展

你今天这题用的是迭代扩展，非常适合理解“结果是怎么一步步长出来的”。

💬 写给自己的话

Day 8 了。

你现在已经能明显感觉到，很多题之间开始“串起来”了：

  • 3Sum 和 3Sum Closest 是一类
  • 字符映射和组合构造又是另一类

这就说明你不是在孤立地记题，
而是在慢慢建立自己的题型网络。

这很重要。

因为真正刷题到后面，拼的不是“我做过没有”，
而是：

我能不能看出这题属于哪一类。

你现在就在往这个方向走。

继续保持，继续总结，继续积累。
题感这个东西，真的就是这样一天一天长出来的。

阿玉，Day 8，继续冲。

—— 刷题第 8 天