LeetCode: twoSum Problem

The twoSum problem is a classic coding challenge that tests your problem-solving and algorithmic skills.

In this post, we’ll first look at a straightforward solution that’s easy to understand. Then, we’ll optimize it step by step to improve its efficiency. Whether you’re new to algorithms or preparing for interviews, this guide will help you master the problem. Let’s get started!

let inputArray = [2, 7, 11, 15]
let target = 9
console.log(twoSum(inputArray, target)) // Output: [0, 1]

Let's look at the input and output the function should handle.

Given the array [2,7,11,15] and a target of 9, the output will be [0,1].

This is because the values at indices 0 and 1 add up to 9, which is the target.

function twoSum(nums, target) {
  const hashMap = {}
}

We will think of a solution where we create a hashMap to store the number in the array as the key and its index as the value.

function twoSum(nums, target) {
  const hashMap = {}

  for (let i = 0; i < nums.length; i++) {
    hashMap[nums[i]] = i
  }
}

This is the first part of the solution: preparing the hashMap.

In the next loop, we check if the hashMap contains the complement of the target minus the current number in the array.

function twoSum(nums, target) {
  const hashMap = {}

  for (let i = 0; i < nums.length; i++) {
    hashMap[nums[i]] = i
  }

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i]

    if (hashMap[complement] !== undefined && hashMap[complement] !== i) {
      return [i, hashMap[complement]]
    }
  }
}

If the complement is found in the hashMap, we can access its index since we have its value.

Then, we can return an array containing its value (the index of the complement) along with i, which represents the current iteration.

In this solution, we see that we are creating two separate loops. We can combine them into a single loop, thereby saving one iteration.

function twoSum(nums, target) {
  const hashMap = {}

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i]

    if (hashMap[complement] !== undefined && hashMap[complement] !== i) {
      return [i, hashMap[complement]]
    }
    hashMap[nums[i]] = i
  }
}

We refined the condition for better clarity and obtained the following code:

function twoSum(nums, target) {
  const hashMap = {}

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i]

    if (complement in hashMap) {
      return [i, hashMap[complement]]
    }
    hashMap[nums[i]] = i
  }
}

let inputArray = [2, 7, 11, 15]
let target = 9
console.log(twoSum(inputArray, target)) // Output: [0, 1]

The above is the detailed content of LeetCode: twoSum Problem. For more information, please follow other related articles on the PHP Chinese website!