2 Sum algorithm explantion?-CodePudding

I am a noobie in JavaScript algorithm and cannot understand this optimal solution of the 2-sum

function twoNumberSum(array, target) {


const nums = {};

  for (const num of array) {
    const potentialMatch = target - num;
    console.log('potential', potentialMatch);
    if (potentialMatch in nums) {
      return [potentialMatch, num]
    } else {
      nums[num] = true;
    }
  }
}

I understand till the console.log line, however I am lost at the If statement, can anyone explain to me how its comparing the numerical values to add up the target sum?

CodePudding user response：

Let me explain to you what it's all is working-.

function twoNumberSum(array, target) {

    // This is and object in Javascript
    const nums = {};

    for (const num of array) { // This is for of loop which iterates the array.
        //For of Doc - https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/for...of

        // Here's its calculating the potential.
        const potentialMatch = target - num;
        console.log('potential - '   potentialMatch);

        /**
         * Nowhere `in` is used which check if any property exists in an object or not.
         * in Usage - https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/in
         * 
         * It checks whether potential exists in the `nums` object, If exist it returns the array
         *   with potentialMatch and num to which it is matched.
         * 
         * If the number is not there in nums object. It's setting there in else block 
         * to match in net iteration.
         */
        if (potentialMatch in nums) {
            return [potentialMatch, num]
        } else {
            nums[num] = true;
            /**
             * It forms an object when the potential match doesn't exist in nums for checking in the next iteration
             * {
             *      1: true,
             *      2: true
             * }
             */
        }
        console.log(nums)
    }
}

console.log(twoNumberSum([1, 2, 4, 5, 6, 7, 8], 3))

You can also Run it from JSBin

CodePudding user response：

So the 2-sum problem basically says "find two numbers in an array that sum to the given target, and return their index". Let's walk through this code and talk about what's happening.

First, we start the function; I'm going to assume this makes sense (a function that's called twoNumberSum that takes in two arguments; namely, array and target) - note that in JS, we don't annotate types, so there is no return type

Now, first thing we do is create a new object called nums. In JS, objects are effectively hash maps (with some very important differences - see my note below); they store a key and a corresponding value. In JS, a key can be any string or number

Next, we start our iteration. If we do for (const a of b), and b is an array, this iterates over all the values of the array, with each iteration having that value stored in a.

Next, we subtract our current value from the target. Then comes the key line: if (potentialMatch in nums). The in keyword checks for the existence of a key: 'hello' in obj returns true if obj has the key 'hello'.

In this case, if we find this potential match, then that means we have found another number that is equal to target - num, which of course means we've found the other partner for our sum! So in this case, we simply return the two numbers. If, on the other hand, we do not find this potentialMatch, that means we need to keep looking. But we do want to remember we've seen this number - thus, we add it as a key by doing nums[num] = true (this creates a new key-value pair; namely the key is num and the value is true).

As one of the comments explained, this is just trying to keep track of a list of numbers; however, the author is trying to be clever by using a Hash Table instead of a normal array. This way, lookups are O(1) instead of O(n). For eyes not used to JS semantics, another way of explaining this code is that we build up a Map of the numbers, and then we check that map for our target value.

I mentioned earlier that using objects as hash tables isn't the best idea; this is because if you aren't careful, if you use user-provided keys, you can accidentally mess with what's called the Prototype Chain. This is beyond this discussion, but a better way forward would be to use a Set:

function twoNumberSum(array, target) {
// Create a new Hash Set. Sets take in an iterable, so we could
// Do it this way. But to remain as close to your original solution
// as possible, we won't for now, and instead populate it as we go
// const nums = new Set(array);

const nums = new Set();
for (const num of array) {
  const potentialMatch = target - num;
  if (nums.has(potentialMatch)) {
    return [potentialMatch, num];
  } else {
    nums.add(num);
  }
}

Sometimes, the problem instead asks for you to return the indices; using a Map instead makes this relatively trivial. Just store the index as the value and you're good to go!

function twoNumberSum(array, target) {
// Create the new map instead

const nums = new Map();
for (let n = 0; n < array.length;   n) {
  const potentialMatch = target - array[n];
  if (nums.has(potentialMatch)) {
    return [nums.get(potentialMatch), n];
  } else {
    nums.set(array[n], n);
  }
}