LeetCode-15.三数之和

发表于 分类于

题目描述

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

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

示例

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

提示：

  • 0 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
func threeSum(_ nums: [Int]) -> [[Int]] {
  guard nums.count >= 3 else {
    return []
  }
  let numbers = nums.sorted(by: <) // 先将数组从小到大排序
  var res = [[Int]]()
  for (index, value) in numbers.enumerated() {
    if value > 0 { // 找每个组合的第一个元素就大于0，后面的只会更大，不可能有和为0的组合
      break
    }
    if index > 0 && numbers[index - 1] == value {
      continue // 如果当前元素跟前一个元素相等，进入下一轮遍历
    }
    var left = index + 1
    var right = numbers.count - 1
    while left < right {
      let sum = value + numbers[left] + numbers[right]
      if sum == 0 {
        res.append([value, numbers[left], numbers[right]])
        left += 1
        right -= 1
        // left后移到跟当前组合中的left位置元素不相等的位置
        while left < right && numbers[left] == numbers[left - 1] {
          left += 1
        }
        // right前移到跟当前组合中的right位置元素不相等的位置
        while left < right && numbers[right] == numbers[right + 1] {
          right -= 1
        }
      } else if sum < 0 {
        left += 1
      } else {
        right -= 1
      }
    }
  }
  
  return res
}