三数之和 | 前端芯事

暴力求解

暴力只需要三重循环，然而我们知道 n^2 的复杂度一般我们就已经不能接受了，这里就不实现了。

但是我们可以利用双指针去求解。

双指针

由于原数组本身无序，我们可以事先最一下排序，这有助于我们利用有序的性质，使用双指针。

基本思路是，固定第一个位置的数字，随后两个指针分别指向下一个数字，和末尾的数字。

如果它们的和小了，那就移动第一个指针；如果大了，那就移动末尾的指针。

由于可能存在重复的数字，而答案要求我们不包含重复，我们可以在移动左指针时判断，如果移动后依然是原数字，就继续移动。我高亮了关键代码。

上一步，我犯过了一个错误，我试图在 while 循环的一开始做这个操作，这会导致我们漏掉一些三元组。因为我们过于提前移动了，虽然是重复的数字，但是这个数字是有可能被右指针使用的，所以会导致漏答案。

而等我们得到一次答案后，下一次又遇到了同样的值，我们这时候去快速跳过重复，这样是安全的了。

当然，我们完全可以先忽略去重的事情，在返回前做去重操作，但这无疑会增加代码量。

额外的，我们可以做亮点小优化：

如果最小值，已经大于我们的目标了，i + 1 和 i + 2 时，我们可以提前跳出循环结束。
同样的，最大值已经小于我们的目标，即 nums.length - 1 和 nums.leng - 2 时，我们可以提前跳出循环。

同样，上面两步我也高亮了代码。

typescript

function threeSum(nums: number[]): number[][] {
  nums.sort((a, b) => a - b);

  const ans: number[][] = []

  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === nums[i-1]) {
      continue;
    }

    const target = -nums[i];

    let left = i + 1;
    let right = nums.length - 1;
    
    if (nums[left] + nums[left+1] > target) { 
      continue 
    } 
    
    if (nums[right] + nums[right-1] < target) { 
      continue 
    } 

    while (left < right) {
      if (nums[left] + nums[right] < target) {
        left++;
      } else if (nums[left] + nums[right] > target) {
        right--;
      } else {
        ans.push([-target, nums[left], nums[right]])
        left++;
        while (nums[left] === nums[left-1]) { 
          left++; 
        } 
        right--;
        while (nums[right] === nums[right+1]) { 
          right--; 
        } 
      }
    }
  }

  return ans
};

暴力求解 ​

双指针 ​

暴力求解

双指针