@tesla809/

Scratch pad

Nodejs

Scratch pad

fork
loading
Files
  • index.js
index.js
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
/*
Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

const arr = [2, 7, 11, 15];

const twoSum = function(nums, target) {
  // hash tables have O(1) running time.
  // use instead of arrays with O(n) time.
  // trade space over time.
  const hashTable = {};
  const resultSumsArr =[];
  const length = nums.length;

  // loop over array
  for(let i = 0; i < length; i++) {
    // subtract element from target
    // since we are looking for two integers
    // that add up to target, by subtracting 
    // one integer, we can get the other.
    let integer1 = target - nums[i];

    // if found in hash table, its it
    // Aka the integer if the integer is found 
    // in the table, then we have our matching pair!
    // this is more efficent than using double loop
    // of O(n^2) time.
    if (hashTable[integer1] !== undefined) {
      resultSumsArr.push(nums[i], integer1);
    } 

    // if not found, add to object aka hashmap
    // key is string representation of integer, value is integer. 
    hashTable[nums[i].toString()] = nums[i];
  }
  // return answer
  return resultSumsArr;
};

const answer = twoSum(arr, 9);
console.log(answer);

/*
Lesson:
-The naive solution isn't probably NOT the best one.
- Learn the different data structures and their benefits, like what hashmaps are. 
-Understand time complexity.
-Look at the STRUCTURE of the problem. See how it can be used to solve it. Focus on the structure before looking at any implementation. Understand the structure of the numbers, their relations and their properties. Play with them and see what else you derive from them.
*/
node v10.16.0