How to find two indices that sum to a specific value

JavaScript, algorithms, arrays

Here is one way to find two indices in an array of numbers that sum to a specific value.
Space complexity: O(n)
Time complexity: O(n)

This approach uses a hash table to record all entries in the array and then loops through the entries to find a complementary pair.
Another solution which optimizes space complexity by increasing time complexity involves sorting the array and using two pointers.

twoSumTry in REPL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
function twoSum(nums, target) {
    const values = nums.reduce((map, num, index) => {
        map[num] = index;
        return map;
    }, {});
    
    for (let i = 0; i < nums.length; i++) {
        const num = nums[i];
        if (values[target-num] !== undefined) {
            return [values[num],values[target-num]];
        }
    }
    return null;
}
// ==== Tests
function runTests(func) {
  const inputOutput = [[[1, 3, 2, -7, 5], 7, [2, 4]]];;
  
  for (let i = 0; i < inputOutput.length; i++) {
    const input = inputOutput[i].slice(0, inputOutput[i].length-1);
  
    const expected = inputOutput[i][inputOutput[i].length-1];
    const result = func(...input);
    
    if (!deepEquals(result, expected)) {
      return `Test failed: Expected - ${expected}. Got ${result}`;
    }
  }
  return 'All tests passed!'
}
// Test cases
// twoSum([1, 2, 3, , -7, 5], 7) //=> [2, 4]
// ==== Test helpers
function deepEquals(x, y) {
  if ((typeof x === "object" && x !== null) && (typeof y === "object" && y !== null)) {
    if (Object.keys(x).length != Object.keys(y).length)
      return false;
    for (var prop in x) {
      if (y.hasOwnProperty(prop))
      {  
        if (!deepEquals(x[prop], y[prop]))
          return false;
      }
      else
        return false;
    }
    return true;
  }
  else if (x !== y)
    return false;
  else
    return true;
}
runTests(twoSum); // All tests passed

Tests can be found at REPL.it