三数之和

let nums = [-1, 0, 1, 2, -1, -4]

• 解法一: 暴力三循环嵌套
• 时间复杂度 O(n^3)

function threeSum(arr) {
  let result = []
  for(let i = 0; i < arr.length; i++) {
    for(let j = i + 1; j < arr.length; j++) {
      for(let k = j + 1; k < arr.length; k++) {
        if(arr[i] + arr[j] + arr[k] === 0) {
          result.push([arr[i], arr[j], arr[k]])
        }
      }
    }
  }
  return result
}

• 解法二: 时间换空间
  • 原理同 javaScript 之两数之和 中的解法二
• 时间复杂度 O(n^3)

function threeSum(arr) {
  let result = []
  let hash = {}
  for(let i = 0; i < arr.length; i++) {
    for(let j = i + 1; j < arr.length; j++) {
      if(hash[arr[j]] !== undefined) {
        result.push([arr[j]].concat(hash[arr[j]]))
        hash[arr[j]] = undefined
      } else {
        let mark = 0 - arr[i] - arr[j]
        hash[mark] = [arr[i], arr[j]]
      }
    }
  }
  return result
}

• 更优解敬请期待