Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

Example

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

JavaScript code

function twoSum(numbers, target) {
    var map = [];
    var result = [];
 
    for (var i = 0; i < numbers.length; i++) {
        if (map[numbers[i]] != null) {
            index = map[numbers[i]];
            result[0] = index+1 ;
            result[1] = i+1;
            break;
        } else {
            map[target - numbers[i]] = i;
        }
    }
 
    return result;
}

console.log(twoSum([1,2,3,4,5,6,7],5));

When Input Array Sorted

If input array is sorted, we don't need to process all items in that array. Observe below code and demo

JavaScript code

function twoSum(numbers, target) {
    if (numbers == null || numbers.length == 0)
        return null;
 
    var i = 0;
    var j = numbers.length - 1;
 
    while (i < j) {
        var x = numbers[i] + numbers[j];
        if (x < target) {
            ++i;
        } else if (x > target) {
            j--;
        } else {
            return [i + 1, j + 1 ];
        }
    }
 
    return null;
}

console.log(twoSum([1,2,3,4,5,6,7],5));

Datastructur Design

Design and implement a TwoSum class. It should support the following operations: add and find.

add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.

example :

add(1); 
add(3); 
add(5);
find(4) -> true
find(7) -> false

JavaScript Code

var elements = [];

function add(number) {
    if (elements[number]!=null) {
        elements[number] = elements[number] + 1;
    } else {
        elements[number]= 1;
    }
}

function find(value) {
    for (var i in elements) {
        var target = value - i;
        if (elements[target] != null) {
            if (i == target && elements[target] < 2) {
                continue;
            }
            return true;
        }
    }
    return false;
}

add(1); 
add(3); 
add(5);

console.log(find(4));
console.log(find(6));
console.log(find(7));

0 comments:

Blogroll

Follow this blog by Email

Popular Posts