三数之和

作者:guo-zi-xin

更新于:9 个月前

字数统计:771 字

阅读时长:2 分钟

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

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

示例

javascript

给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

夹逼原则 夹逼原则，也称为双指针夹逼法，是一种常用的算法思想，主要用于解决某些数组或有序列表中的查找、求解等问题。该原则基于两个指针在数组或列表中相向而行，并通过调整指针的位置来逼近目标值或满足特定条件。在夹逼原则中，通常需要先对数组或列表进行排序，以便使用双指针从两端开始向中间移动。具体步骤如下：
1. 对数组或列表进行排序，确保元素的顺序满足问题的要求。
2. 初始化两个指针，一个指向数组或列表的起始位置（通常是最左侧），另一个指向数组或列表的结束位置（通常是最右侧）。
3. 在两个指针没有相遇之前，进行如下操作：
  - 比较指针所指向的元素与目标值或特定条件的关系。
  - 根据比较结果，调整指针的位置：
    - 如果指针所指向的元素满足条件，可以得到问题的解，或进行其它操作。
    - 如果指针所指向的元素不满足条件，根据问题的要求，将指针向中间移动一步或多步。
4. 继续移动指针，直到两个指针相遇。夹逼原则的核心思想是通过双指针的相向移动，将问题的解空间逐渐缩小，直到找到满足条件的解或遍历完所有可能的情况。

夹逼原则常用于解决一些查找问题，比如在有序数组中查找目标值、找出数组中三个数的和等。它的优势在于时间复杂度较低，通常为 O(n) 或 O(nlogn)，具体取决于排序的时间复杂度。

需要注意的是，在使用夹逼原则时，要保证数组或列表已经有序，否则可能会得到错误的结果。此外，对于一些特殊情况，还需要考虑边界条件和指针移动的终止条件，以确保算法的正确性。

typescript

  const threeSum = (nums: number[]): Array<number[]> => {
    const len = nums.length
    const result:Array<number[]> = []
    if (len <  3) {
      return []
    }
    nums.sort((a, b) => a - b)
    for (let  j = 0; j< len - 2; j++) {
      if (nums[j]>  0 ) {
        break
      }
      if (j && nums[j] === nums[j - 1]) {
        continue
      }
      let left = j + 1
      let right = len - 1
       // 双指针夹逼
      while (left < right) {
        const sum = nums[j] + nums[left] + nums[right]
        if (sum === 0) {
          result.push([nums[j],  nums[left++], nums[right--]])
          while(nums[left]  === nums[left - 1]) {
            left++
          }
          while(nums[right]  === nums[right + 1]) {
            right++
          }
        } else if (sum > 0) {
          right--
        }else {
          left ++
        }
      }
    }
    return result
  }
  const nums: number[] = [0, -1, 1, 2, 3, -3]
  console.log(nums)
  console.log(threeSum(nums))

三数之和 ​

三数之和