三数之和

如果说两数之和是梦开始的地方，那么三数之和就是梦破碎的地方，这个题目要求我们找出所给数组中的所有的三元组之和等于零的元素，并且要求不重复。

分析过程

问题描述

给定一个包含 n 个整数的数组 nums，我们需要判断 nums 中是否存在三个元素 a、b、c 使得 a + b + c = 0。需要找出所有满足条件且不重复的三元组。

示例

输入：nums = [-1, 0, 1, 2, -1, -4]，输出：[[-1, -1, 2], [-1, 0, 1]]
输入：nums = []，输出：[]
输入：nums = [0]，输出：[]

算法步骤

排序：首先对数组进行排序，以便后续操作能够使用双指针法。

遍历：使用一个循环遍历数组，每次固定一个数 nums[i]，然后使用双指针方法在 i 之后的数组中寻找另外两个数使得三者之和为零。

跳过重复元素：为了避免重复的三元组，如果当前数和前一个数相同，则直接跳过。

双指针法：
初始化两个指针，左指针 left 指向 i 的下一个元素，右指针 right 指向数组的最后一个元素。
计算 nums[i] + nums[left] + nums[right] 的和：
如果和小于零，左指针右移；
如果和大于零，右指针左移；
如果和等于零，找到一个三元组，将其添加到结果列表，并移动左右指针以跳过相同的元素。

复杂度分析

时间复杂度：排序的时间复杂度为 O(n log n)，遍历数组和使用双指针查找的时间复杂度为 O(n^2)，所以总体时间复杂度为 O(n^2)。
空间复杂度：由于使用了排序和额外的存储结果列表，空间复杂度为 O(n)。

代码

复制代码
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const threeSum = (nums) => {
  const result = [];
  nums.sort((a, b) => a - b); // 对数组进行排序
  const len = nums.length;
  
  for (let i = 0; i < len; i++) {
    if (nums[i] > 0) break; // 第一个数大于0，后面的数相加不可能为0
    if (i > 0 && nums[i] === nums[i - 1]) continue; // 跳过重复元素
    
    let left = i + 1;
    let right = len - 1;
    
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      if (sum < 0) {
        left++;
      } else if (sum > 0) {
        right--;
      } else {
        result.push([nums[i], nums[left], nums[right]]);
        while (left < right && nums[left] === nums[left + 1]) left++; // 跳过重复元素
        while (left < right && nums[right] === nums[right - 1]) right--; // 跳过重复元素
        left++;
        right--;
      }
    }
  }

  return result;
};

总结

我们详细分析了一个寻找数组中所有和为零的三元组的算法。该算法通过排序和双指针方法有效地解决了问题，避免了重复的三元组，并在合理的时间复杂度内完成了任务。理解和掌握这种算法，不仅有助于解决类似的问题，还能提升我们在处理数组问题时的编程技巧和思维能力。希望这篇博客对你有所帮助！