算法-N数の合計

2 つの数の合計は、それは LeetCode で最も基本的な問題です。以下では解法を分析します。

第一の解法#

配列をループして、目標値 - 現在のループ値 => 別の値、各ループで現在の値をマップに保存し、マップ内に別の値が存在する場合は、対応するインデックスを取り出して現在のループ値と組み合わせて返します。

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

第二の解法#

第二の解法は、2 つのポインタを使用して解決します。

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){
      // 2つの数が目標より大きい場合、右の範囲を縮小する
      right--
    } else if(nums[left] + nums[right] < target){
      // 2つの数が目標より小さい場合、左の範囲を拡大する
      left++
    } else {
      // 等しい場合、インデックスを返す
      left = list.indexOf(nums[left])
      right = list.lastIndexOf(nums[right])
      return [left, right]
    }
  }
  return []
}

3 つの数の合計#

2 つのポインタを使用して、各項目をループし、現在のループ項目の次の項目から 2 つのポインタ操作を行い、条件を満たす結果を返すまで続けます。

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