Leet Code | Two Sum Solution

twoSum.md

LeetCode | TwoSum

Difficulty: ✅☑☑☑☑

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]
Output: 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]

Solution

Leet Code | Report

Performance

Upper Bound: O(log n) Lower Bound: Ω(1)

I designed this solution to try to get around using a for loop within a for loop, which is o(n^2).

Each time we iterate the array, we no longer iterate the same value again, which I believe would make the upper bound o(log n).

We could also be lucky enough that it's the first pair we test, giving us a lower bound of Ω(1).

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
    // Avoiding a for loop, we won't have an index
    let currentIndex = 0;
    let result = [];
    while(result.length < 2 && nums.length) {
        // Split array and test the 0th case against the remaining array
        let testVal = nums.shift();
        try {
            nums.forEach((num, ind) => {
                // Using our try we can abort with a throw as soon as we hit the target
                if(testVal + num === target) {
                    throw ind;
                }
            });
        } catch (num) {
            result = [currentIndex, num + (currentIndex + 1)];
            console.log(testVal, num);
        }
        currentIndex++;
    }

    return result;

};