Is there a way to make this code simplier?

Question

Program description:

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

My solution:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
  let N = nums.length;  
  for(i=0;i<=N-1;i++) {
      for(j=i+1;j<=N;j++) {
          if(nums[i] + nums[j] == target) {
              return [i,j];
          };
      };
  };  
};

Test input:

[2,7,11,15]
9

Test output:

[0,1]

Test summary:

Solution accepted.
Runtime: 84ms

Question: is there a way to make this code look more neat using some comprehensions, maybe also improving its runtime? Thank you in advance.

Answer 1

Performance The biggest issue with your current implementation is that it's O(n ^ 2). You have to iterate through an array of length N (N ^ 2) / 2 times in order to find matches. The algorithm can be improved by iterating only once, and by using a Set or an object when iterating to store which number the current number would have to be paired with in order to sum to the target.

For example, when iterating over 1, with a target of 5, you could put 4 into the Set, because 1 + 4 === 5. On further iterations, check to see if the element being iterated over exists in the Set. If it does, it's a match: return the pair. See bottom of answer for an implementation.

Prefer const over let Since N isn't being reassigned, declare it with const: https://softwareengineering.stackexchange.com/questions/278652/how-much-should-i-be-using-let-vs-const-in-es6

Don't create global variables Always declare variables before using them. Your current code with for(i=0;i<=N-1;i++) and for(j=i+1;j<=N;j++) { is implicitly creating global i and j variables. This is both inelegant and can lead to confusing bugs if the function gets called again before its first call completes. (Also consider adding spaces between operators for readability). You'd want to do:

for (let i = 0; i < N; i++) {

Note the use of i < N, not i <= N; since N is the length, nums[N] will be undefined, so you shouldn't iterate over it.

Use strict equality Don't use == - it has many strange rules with type coercion. Even if you're sure the types of the operands are the same, to make it clearer for readers at a glance, better to avoid it and use === or !== instead.

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = function(nums, target) {
  // Key: Number which, if found, matches the number at the index value
  // eg: { 3 => 6 }: if 3 is found later, it'll be a match with the number at index 6
  const indexByPair = new Map();
  const { length } = nums;
  for (let i = 0; i < length; i++) {
    if (indexByPair.has(nums[i])) {
      return [indexByPair.get(nums[i]), i];
    }
    indexByPair.set(target - nums[i], i);
  }
};
console.log(twoSum([2,7,11,15], 9));