Question

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

• 2 <= nums.length <= 104
• 109 <= nums[i] <= 109
• 109 <= target <= 109
• Only one valid answer exists.

My Solution

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let leng = nums.length
    for( i=0; i<leng; i++ ){
            for(t = i + 1; t < leng; t++){
            if (nums[i] + nums[t] == target){
                return [i, t]
            }
        }
    }
};

Better Solution

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        let diff = target - nums[i];
        if(map.has(diff)){
            return [map.get(diff), i]
        }
        map.set(nums[i], i)
    }
}

Key Takeaways

While my initial solution successfully solves this Leetcode problem, its time complexity of O(n2)O(n^2)O(n2) leaves room for improvement. To optimize the performance, we can leverage a Hash Table. This approach allows us to efficiently store and look up elements as we iterate through the array.

Optimized Approach: Hash Table

The idea is simple:

1. Use a hash table to record each number we iterate over, along with its index.
2. For each number in the array, check if its complement (i.e., target - currentNumber) exists in the hash table.
3. If found, return the indices of the current number and its complement.

This optimized approach improves the time complexity to O(n), making it significantly faster and more suitable for large datasets.