数组与字符串之三数之和

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

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

示例

给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

分析

对数组进行排序然后采用双指针解, 从左侧开始选定一个”定值”, 右侧进行求解, 获取与其相加为0的两个值., 值小于0时左指针右移, 大于0时右指针左移, 否则定值右移重复以上步骤. 时间复杂度排序O(nlogn), 双指针遍历O(n), 遍历数组O(n), 总消耗为O(nlogn) + O(n) + O(n) = O(n^2)

代码

Python3

def threeNumberSum(self, nums):
  res = []
  numsLen = len(nums)

  if (not nums or numsLen < 3):
    return []

  nums.sort()
  for i in range(numsLen):
    if (nums[i] > 0):
      return res
    if (i > 0 and nums[i] == nums[i - 1]):
      continue
    left = i + 1
    right = numsLen - 1
    while (left < right):
      if (nums[i] + nums[left] + nums[right] == 0):
        res.append([nums[i], nums[left], nums[right]])
        # 左指针右移
        while (left < right and nums[left] == nums[left + 1]):
          left = left + 1
        # 右指针左移
        while (left < right and nums[right] == nums[right - 1]):
          right = right - 1
        left = left + 1
        right = right - 1
      elif (nums[i] + nums[left] + nums[right] > 0):
        right = right - 1
      else:
        left = left + 1
  return res

JavaScript

function threeNumberSum(nums) {
  let res = []
  nums.sort((a, b) => a - b)
  let len = nums.length

  if (nums[0] <=0 && nums[len - 1] >= 0) {
    let i = 0

    while (i < len - 2) {
      // 最左侧大于0结果必然大于0无解
      if (nums[i] > 0) break

      let left = i + 1
      let right = len - 1
      while (left < right) {
        // 三数符号相同无解
        if (nums[i] * nums[right] > 0) break
        let sum = nums[i] + nums[left] + nums[right]
        if (sum === 0) {
          res.push([nums[i], nums[left], nums[right]])
        }
        if (sum <= 0) {
          // 跳过重复元素
          while(nums[left] === nums[++left]) {}
        } else {
          while(nums[right] === nums[--right]) {}
        }
      }
      while(nums[i] === nums[++i]) {}
    }
  }
  return res
}