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.
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:
Post a Comment