How can I decrease the time spent checking each value in this leetcode?-CodePudding

So on LeetCode, I need to return the sum of two numbers that equal the target number. This is a leetcode "easy" type. I've never done leetcode before so I decided to give it a try. Right off the bat, I was able to solve the problem but my solution was nonsenical because it checks each number in the array against eachother. So if the input is a million digits then it will check it a million times for each number.

It's worth noting that although my program works, it can be submitted due to time limit exceeding.

I'm not sure what the mathematical solution would be to opitmize this. I'm currently going to Maths again learning what I am weak at.

Code:

var twoSum = function(nums, target) {
  let total = [];
    let inc = 1;
    let intVal = 0;
    
    let startingPos = nums[intVal];
    let nextPos = nums[inc];
    
    for(let x = 0; x < nums.length; x  ){
        // Do not check the value of position 1 with position 2
        if(nums.indexOf(startingPos) === nums.lastIndexOf(nextPos)){
            nextPos  ;
        }
        
        if(startingPos   nextPos === target){
            console.log(`First Value ${startingPos}`)
            console.log(`Second Value ${nextPos}`)
            console.log(`Target ${target}`)

            // A match has been found
            return [nums.indexOf(startingPos), nums.lastIndexOf(nextPos)];
        } else{
            // Move to next number if index 1 is not eql
            // nextPos  ;
            let nextPosIndex = nums[inc];
            
            nextPos = nums[inc];
            console.log(`Values [${startingPos}], [${nextPos}]`)
            console.log("No Matches");

            // Increment the next value to check
            inc  ;

            // Reset loop if no match is found from 2nd position
            if(x == (nums.length - 1)){
                // Increment the initial value in first pos
                intVal  ;
                startingPos = nums[intVal];

                // Reset values to check new numbers
                x = 0;
                inc = 1;
            } 

            // check if we exhausted all options
            if(startingPos === undefined){
                return "No Matches.";
            }
        }

        
    }
};

twoSum([5, 2, 5, 5, 1, 3, 6, 8, 4, 3, 2, 7], 14)

-- Before proceeding to any more problems, I am afraid I will be in this loop of choosing the most illogical way of solving the problems.

What can I do to modify this problem to quickly check if two values equals the target.

Here is a live compiler example: https://replit.com/@FPpl/SafeHeartfeltArchitect#index.js

CodePudding user response：

When iterating over a number, you can put the value that, if it would match to sum to the target, into a collection (with O(1) lookup). For example, if you iterate over a number 5, and the target is 20, put 15 into the collection.

During an iteration, if the number being iterated over already exists in the collection, you have a match from one you found previously, and you can return both indicies.

const twoSum = function(nums, target) {
  // For this Map, the key is the number which, if found again, is a match
  // eg, if target is 20, and the number 5 is iterated over
  // the key will be 15
  // The value is the index of the prior number found - eg, index of 5
  const valuesAlreadyFound = new Map();
  for (let i = 0; i < nums.length; i  ) {
    const num = nums[i];
    if (valuesAlreadyFound.has(num)) {
      // We have a match, get both indicies:
      console.log('Match for values', target - num, num);
      return [valuesAlreadyFound.get(num), i];
    }
    // This wasn't a match. Identify the number which, when paired, is a match
    const matchNeeded = target - num;
    valuesAlreadyFound.set(matchNeeded, i);
  }
  return 'No match';
};

console.log('Indicies found:', twoSum([5, 2, 5, 5, 1, 3, 6, 8, 4, 3, 2, 7], 14));