三数之和

共计 334 字，约需阅读 1.21 分钟

leetcode 算法题

暴力求解

三层循环遍历数组把符合条件的数据放入数组之中，然后再去重，时间复杂度 nnn 再加去重时间

优化暴力求解

数组排序，然后遍历数组，把数据放入对象中去重，避免最后的去重操作，时间复杂度 nnn

双指针方法

数组进行排序，然后外层循环固定一个数，内层使用两个指针分别指向数组的左右两边，如果三数之和小于 0 则把左边指针右移，若果三数之和大于 0 则把右边指针左移，等于 0 时判断数组是否已经存在结果数组中，若存在则跳过，不存在放入数组并在 map 中标记

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var threeSum = function (nums) {
  const sortNums = nums.sort((a, b) => a - b)
  const len = sortNums.length
  const result = []
  const obj = {}
  for (let i = 0; i < len - 2; i++) {
    let left = i + 1
    let right = len - 1
    while (left < right) {
      if (sortNums[i] + sortNums[left] + sortNums[right] > 0) {
        right = right - 1
      } else if (sortNums[i] + sortNums[left] + sortNums[right] < 0) {
        left = left + 1
      } else if (sortNums[i] + sortNums[left] + sortNums[right] === 0) {
        if (!obj[`${sortNums[i]},${sortNums[left]},${sortNums[right]}`]) {
          result.push([sortNums[i], sortNums[left], sortNums[right]])
          obj[`${sortNums[i]},${sortNums[left]},${sortNums[right]}`] = true
        }
        left = left + 1
      }
    }
  }
  return result
}