代码随想录算法训练营第7天｜哈希表Part02

记录题目：

• 三数之和
• 四数之和
• 赎金信

---

• 三数之和

• 四数之和

• 赎金信

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

LeetCode15. 三数之和

• 在 threeSum 中，必须注意值和下标的区别，三元组加入结果后要及时移动指针并去重， 否则容易造成重复结果或死循环。

• 提前终止无效枚举 if (nums[i] > 0) break; 这条语句的威力非常大！

  • nums 是升序的，一旦最小值都大于 0， 后面 nums[i] + nums[left] + nums[right] > 0 一定永远不会等于 0。

  • 所以这条剪枝可以提前跳出主循环，直接减少上百上千次不必要的遍历。 时间复杂度虽然还是 O(n²)，但实际遍历次数可能减少一半甚至更多。 即使是 O(n²)，也能在工程实现上有非常明显的“快慢之分”！这种常数项优化在刷题实战中非常关键。

• 对于 sum 不等于 0 的情况， left 和 right 不用去重，因为这个组合不会被推入结果数组。

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

LeetCode18. 四数之和

去重条件

在固定 j 时如果使用：

// ...
for (let i = 0; i < len - 3; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    for (let j = i + 1; j < len - 2; j++) {
        if (j > 0 && nums[j] === nums[j - 1]) continue;
        // 去重条件错误，会跳过合法组合
        // 这种写法下标 j - 1 可能未曾被 j 指向过，但却会判断 j 指向过相同数而 continue
        let left = j + 1, right = len - 1;
        while (left < right) {
// ...

这里的 j > 0 是错误的，应该是：

if (j > i + 1 && nums[j] === nums[j - 1]) continue;

原因：我们要确保在同一个 i 下，从 i+1 开始的第一个合法 j 被保留，后续重复的才跳过。

剪枝（提前结束判断）可提高效率

在 LeetCode 中，fourSum 数据范围比较大，加入剪枝逻辑可以显著提升运行速度，例如：

// 最小可能值 > target，直接 break
if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;

// 最大可能值 < target，直接跳过
if (nums[i] + nums[len - 1] + nums[len - 2] + nums[len - 3] < target) continue;

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

LeetCode383. 赎金信

charCodeAt() 是 JavaScript 字符串对象的内置方法， 用于返回指定位置字符的 Unicode 编码（UTF-16 编码单元）。

语法：

str.charCodeAt(index)

• str：目标字符串
• index（可选）：字符位置索引（从 0 开始），默认值为 0

特性	详情
返回值类型	数字（Unicode 编码值）
默认参数	index=0
索引越界	返回 NaN
处理代理对	需配合 codePointAt()
常见用途	字符编码转换、加密、字符串处理

如果需要处理复杂的 Unicode 字符（如表情符号），建议优先使用 codePointAt()。对于普通 ASCII 字符，charCodeAt() 已经足够高效。