先来回顾一下上期的问题及答案：

2023年6月14日

「最接近的三数之和」（3Sum Closest）。以下是题目的描述：

给定一个包括 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 (-1 + 2 + 1 = 2) 。

以下是对应的JavaScript解答：

function threeSumClosest(nums, target) {
  nums.sort((a, b) => a - b);
  let closestSum = nums[0] + nums[1] + nums[2];

  for (let i = 0; i < nums.length - 2; i++) {
    let left = i + 1;
    let right = nums.length - 1;

    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];

      if (Math.abs(sum - target) < Math.abs(closestSum - target)) {
        closestSum = sum;
      }

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

  return closestSum;
}

解题思路：

• 首先对数组 nums 进行排序，以便于使用双指针的方法进行查找。

• 初始化一个变量 closestSum，用于记录与目标值 target 最接近的三个数的和，初始值为前三个数的和。

• 遍历数组 nums，使用指针 i 从左往右选取第一个数字。

• 在每个固定的数字 nums[i] 的基础上，使用双指针 left 和 right 分别指向剩余数组中的左右两端。

• 计算当前三个数字的和 sum，并根据与目标值 target 的差值的绝对值判断是否更新 closestSum。

• 根据三个数字的和与目标值的关系进行移动指针：

  • 如果三个数字的和等于 target，则直接返回该和。

  • 如果三个数字的和小于 target，移动 left 指针。

  • 如果三个数字的和大于 target，移动 right 指针。

• 最终返回 closestSum。

时间复杂度分析：

• 数组排序的时间复杂度为 O(nlogn)。

• 双指针的移动最多需要遍历整个数组，时间复杂度为 O(n)。

• 总体时间复杂度为 O(nlogn + n^2)，简化为 O(n^2)。

空间复杂度分析：

• 使用了常数级别的额外空间，空间复杂度为 O(1)。

2023年6月15日

「电话号码的字母组合」（Letter Combinations of a Phone Number）。以下是题目的描述：

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

说明:

• 尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

解题思路：

• 使用回溯法来构建所有可能的字母组合。

• 定义一个映射 mappings，将数字和对应的字母数组进行关联。

• 初始化一个空数组 combinations，用于存储所有的字母组合。

• 编写回溯函数 backtrack，该函数接受两个参数：当前已经组合的字母字符串 current 和剩余的数字字符串 nextDigits。

• 当剩余数字字符串的长度为 0 时，说明已经遍历完所有的数字，将当前组合的字母字符串加入 combinations 数组中。

• 如果剩余数字字符串的长度不为 0，则获取剩余数字字符串的第一个数字对应的字母数组。

• 遍历该字母数组的每个字母，将当前字母与剩余数字字符串的子串进行递归调用 backtrack。

• 最终返回 combinations 数组，即所有可能的字母组合。

上面问题的答案会在第二天的公众号推文中公布，大家可以关注公众号：程序员每日三问，第一时间获得推送内容。

学习不打烊，充电加油只为遇到更好的自己,每天早上9点纯手工发布面试题（死磕自己，愉悦大家） 希望大家在这浮夸的程序员圈里保持冷静，每天坚持花20分钟来学习与思考，在千变万化，类库层出不穷的今天，不要等到找工作时才狂刷题，提倡每日学习。