算法-N数之和

两数之和，它算是 LeetCode 中最基础的题目，下面分析一下解法。

第一种解法#

循环遍历数组，目标值 - 当前遍历值 => 另一值，每次遍历，保存当前值到 map 中，在 map 中存在另一值，存在则取出对应下标，结合当前遍历值返回。

function two_sum (nums, target){
  // 输入需满足条件
  if(!Array.isArray(nums) || nums.length < 2) return []
  const len = nums.length
  // 设置 值->索引映射
  const map = {}
  for(let i = 0; i < len; i++){
    let val = nums[i];
    // 另一值存在map中，则返回索引
    if(map[target - val] !== void 0){
      return [map[target - val], i]
    }
    // 保存值->索引
    map[val] = i
  }
  return []
}

第二种解法#

第二种利用双指针解法

function two_sum (nums, target){
  // 输入需满足条件
  if(!Array.isArray(nums) || nums.length < 2) return []
  let list = nums.slice()
  nums = nums.sort((a, b) => a - b)
  // 头指针
  let left = 0;
  // 尾指针
  let right = nums.length - 1;
  // 不断缩小区间
  while(left < right) {
    if(nums[left] + nums[right] > target){
      // 两数大于目标，右区间减小
      right--
    } else if(nums[left] + nums[right] < target){
      // 两数小于目标，左区间增大
      left++
    } else {
      // 相等，返回索引
      left = list.indexOf(nums[left])
      right = list.lastIndexOf(nums[right])
      return [left, right]
    }
  }
  return []
}

三数之和#

利用双指针，循环每一项，在当前循环项的后一项开始双指针操作，直至返回满足条件结果

function three_sum(nums, target){
    // 输入需满足条件
  if(!Array.isArray(nums) || nums.length < 3) return []
  // 排序数组，存在负数，所以需要特殊处理
  let nNums = nums.filter(i => i < 0).sort((a, b) => a - b)
  let pNums = nums.filter(i => i >= 0).sort((a, b) => a - b)
  nums = nNums.concat(pNums)
  
  let list = nums.slice()
  let len = nums.length;
  // 遍历数组
  for(let i = 0; i < len; i++){
    // 当前数组的下一个作为头指针
    let left = i + 1;
    // 当前数组最后一个作为尾指针
    let right = len - 1;
    while(left < right) {
      if(nums[left] + nums[right] > sum){
        right--
      } else if(nums[left] + nums[right] < sum){
        left++
      } else {
        // 相等，取索引
        left = list.indexOf(nums[left], i + 1)
        right = list.lastIndexOf(nums[right])
        retun [i, left, right]
      }
    }
  }
  return []
}