1
\$\begingroup\$

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 < index2. Please note that your returned answers (both index1 and index2 ) are not zero-based. Put both these numbers in order in an array and return the array from your function ( Looking at the function signature will make things clearer ). Note that, if no pair exists, return empty list.

If multiple solutions exist, output the one where index2 is minimum. If there are multiple solutions with the minimum index2, choose the one with minimum index1 out of them.

twoSum : function(A, B){
        var tempA = A;
        var index1 = [];
        var index2 = [];
        var Results = [];

        for(var i = 0; i < A.length - 1; i++){
            var temp = B - A[i];
            for(var j = i; j < A.length - 1; j++){
                if(temp == A[j]){
                    if(j - i > 0){
                        if(j < Results[1] || Results.length == 0){
                            if(A[j] != A[Results[1]-1] && A[i] != A[Results[0]-1]){
                                Results[0] = i + 1;
                                Results[1] = j + 1; 
                            }
                        }
                    }
                }
            }
        }
        return Results;
    }```
\$\endgroup\$
1
  • \$\begingroup\$ Could you change your title to a more general explanation of what your code does? A question about how to improve your code is implied in all code review question, and is therefore unnecessary. \$\endgroup\$
    – K00lman
    Mar 6 '20 at 17:26
2
\$\begingroup\$

Variables tempA, index1 and index2 seem to be unused.

Since you are only interested in if(j - i > 0){, you can start right there for (int j = i + 1; and omit the conditional.

Further the condition if(j < Results[1] || Results.length == 0){ should be flipped around to if(Results.length == 0 || j < Results[1]){ to avoid accessing undefined index.

But actually the variable Results is uselesss because you can return the pair as soon as you find it. Just iterate in the desired directions.

function twoSum(input, targetSum){
  const limit = input.length;
  for(var j = 1; j < limit; ++j){
    var temp = targetSum - input[j];
    for(var i = 0; i < j; ++i){
      if(temp == input[i]){
        return [i + 1, j + 1];
      }
    }
  }
  return [];
}
\$\endgroup\$
1
\$\begingroup\$

Yes, this should be more efficient asymptotically

function myTwoSum(A, B) {
    const invertedArrayMap = A.reduce((acc, curr, i) => {
        acc[curr] = acc.hasOwnProperty(curr) ? Math.min(i, acc[curr]) : i;
        return acc;
    }, {});

    const secondIndex = A.findIndex(
        (w, i) =>
        invertedArrayMap.hasOwnProperty(B - w) && invertedArrayMap[B - w] < i
    );

    if (secondIndex === -1) {
        return [];
    }
    return [invertedArrayMap[B - A[secondIndex]], secondIndex];
}

We use an object to allow O(1) lookups for the corresponding value, allowing us to not have this nested O(n^2) computation.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.