Algorithm - Sum of N Numbers

The sum of two numbers is considered to be the most basic problem in LeetCode. Let's analyze the solution below.

First solution#

Loop through the array, target value - current value => another value. Each time you traverse, save the current value to the map. If the other value exists in the map, retrieve the corresponding index and return it along with the current traversal value.

function two_sum (nums, target){
  // The input must meet the conditions
  if(!Array.isArray(nums) || nums.length < 2) return []
  const len = nums.length
  // Set value->index mapping
  const map = {}
  for(let i = 0; i < len; i++){
    let val = nums[i];
    // If the other value exists in the map, return the index
    if(map[target - val] !== void 0){
      return [map[target - val], i]
    }
    // Save value->index
    map[val] = i
  }
  return []
}

Second solution#

The second solution uses the two-pointer approach.

function two_sum (nums, target){
  // The input must meet the conditions
  if(!Array.isArray(nums) || nums.length < 2) return []
  let list = nums.slice()
  nums = nums.sort((a, b) => a - b)
  // Head pointer
  let left = 0;
  // Tail pointer
  let right = nums.length - 1;
  // Continuously narrow the range
  while(left < right) {
    if(nums[left] + nums[right] > target){
      // If the sum of the two numbers is greater than the target, decrease the right interval
      right--
    } else if(nums[left] + nums[right] < target){
      // If the sum of the two numbers is less than the target, increase the left interval
      left++
    } else {
      // If they are equal, return the indices
      left = list.indexOf(nums[left])
      right = list.lastIndexOf(nums[right])
      return [left, right]
    }
  }
  return []
}

The sum of three numbers#

Using the two-pointer approach, loop through each item and perform two-pointer operations starting from the next item in the current loop until the result that satisfies the condition is returned.

function three_sum(nums, target){
    // The input must meet the conditions
  if(!Array.isArray(nums) || nums.length < 3) return []
  // Sort the array, as there are negative numbers, special handling is required
  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;
  // Traverse the array
  for(let i = 0; i < len; i++){
    // The next item in the current array becomes the head pointer
    let left = i + 1;
    // The last item in the current array becomes the tail pointer
    let right = len - 1;
    while(left < right) {
      if(nums[left] + nums[right] > sum){
        right--
      } else if(nums[left] + nums[right] < sum){
        left++
      } else {
        // If they are equal, take the indices
        left = list.indexOf(nums[left], i + 1)
        right = list.lastIndexOf(nums[right])
        retun [i, left, right]
      }
    }
  }
  return []
}