Retuning a tuple of indices of two items in an array that add together to a target value

user_16222347 0
Viewed 51

My task is to write a function that takes an array of numbers and a target number

I must find two numbers in the array that add together to form the target, and then return the indices of the two numbers as a tuplet, like so (index1, index2).

I have created a nested for loop to compare each element of the array to each other element, and then ran an if statement to return the indices when the target value has been reached.

However, something is not working. I am not sure how to return as a tuplet or perhaps my code to get the indices is wrong. Any help or hints would be very appreciated. Thank you

function twoSum(numbers, target) {
  for (let i = 0; i < numbers.length; i++) {
    for (let j = 0; j < numbers.length; j++) {
      if (numbers[i] + numbers[j] === target) {
        return [numbers.indexOf(i), numbers.indexOf(j)];
      }
    }
  }
}

tuples for-loop arrays algorithm javascript
2 Answers

Array#indexOf() returns the position of the value passed to the method. So [1,2,3].indexOf(2) would return 1. [numbers.indexOf(i), numbers.indexOf(j)] will give you the position of the current value of your counter variables i and j in the array. If the value isn't in the array, say [1,2,3].indexOf(0), the method will return -1.

The indices you are looking to return are just i and j.

function twoSum(numbers, target) {
  for (let i = 0; i < numbers.length; i++) {
    for (let j = 0; j < numbers.length; j++) {
      if (numbers[i] + numbers[j] === target) {
        return [i, j];
      }
    }
  }
}

console.log(twoSum([1,2,3,4],5)) // 1+4 = 5 => [0,3]
console.log(twoSum([1,2,3,4],9)) // undefined since there is no solution

user_66345910

When the fix [i, j] is applied, this algorithm will work. But it is very inefficient. In particular, when there is no solution, it tries L² pairs.

Now, assume that the array is sorted increasingly. Set i=0 and find the smallest j, scanning from right to left, such that n[i] + n[j] ≥ target. Next, increment i and adjust j to be again the smallest such that n[i] + n[j] ≥ target. And so on, until i and j cross or exact equality is achieved. Now, the number of pairs is of order L only, a quite significant saving. The cost of the sort is proportional to L.log(L).

So a strategy is to sort the array, and look for a matching pair of values as above. To obtain the indexes (in the initial array), you can keep a copy and use indexof. Another option is to augment the array by appending its index to every element, and move them together during the sort.

user_11965490
Related