算法-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 []
}