18

I'm trying to do a LeetCode Two Sum question:

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 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2

The first try was using two for loops, which gave me O(n^2), and unfortunately it didn't pass. Hence I tried to use:

target - current = index

And search for if the index does exists on a dictionary.

This is my code:

class Solution:
    def twoSum(self, nums, target):
        dic = {}
        
        #A number can appear twice inside the same index, so I use a list
        for i in xrange(0, len(nums)):
            try:
                dic[nums[i]].append(i)
            except:
                dic[nums[i]] = []
                dic[nums[i]].append(i)
          
        try:
            for items_1 in dic[nums[i]]:
                for items_2 in dic[target-nums[i]]:
                    if(items_1+1 != items_2+1):
                        l = []
                        if(items_2+1 > items_1+1):
                            l.append(items_1+1)
                            l.append(items_2+1)
                        else:
                            l.append(items_2+1)
                            l.append(items_1+1)
                        return l
        except:
            pass

I developed this locally, and I was able get the correct result with one of the test case that LeetCode was complaining: [-3,4,3,90], 0

The output I got was [1, 3], but on LeetCode it returned null, does anybody know why this would happen?

Improve this question
12
  • Does it really matter if a number appears twice in the nums list? All that matters is that you get a index, correct? Commented May 4, 2015 at 0:54
  • Well... If the number was [0, 3, 4, 0], the correct value should be 1st, and 4th index. However, since 0 index is already at the 1st index, what happens is that the 4th index isn't in the dictionary. Commented May 4, 2015 at 0:57
  • Would you like me to show you how I would write it? Commented May 4, 2015 at 0:58
  • why did you make a class? the class contains nothing but a single method. why not delete the class definition line and leave the method as a stand-alone function? Commented May 4, 2015 at 0:59
  • The class is required to submit the answer, in my local development, I don't have the class included. Commented May 4, 2015 at 1:01

23 Answers 23

Reset to default
16 
def twosum(nums=(6, 7, 11, 15, 3, 6, 5, 3), target=6):
    lookup = dict(((v, i) for i, v in enumerate(nums)))
    return next(( (i+1, lookup.get(target-v)+1) 
            for i, v in enumerate(nums) 
                if lookup.get(target-v, i) != i), None)

This algorithm can be broken up into two stages:

  1. Create a dictionary of value->index for all index, value pairs in nums. Note that you can have multiple values with different indices. In this case, the highest index will be stored in the dictionary and lower indexes will be overwritten. This behavior can be modified, of course, but I don't believe it needs to be for this problem because part of the problem statement is this: "You may assume that each input would have exactly one solution." Thus, each input has a single unique output so we never have to worry about returning a "wrong-pair" of indices.

  2. Loop through the enumeration of nums, getting i as index, and v as value. Check if target-v is a key in the dictionary we created, and simultaneously assert that the value pointed to by that key is not i. If this is ever true, return the tuple i+1, lookup.get(target-v)+1.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

Gives the same exact answer as my code, but why isn't my code accepted? :(
@user1157751 Idk unfortunately, does your code have the same underlying logic as mine? Nuances are important, such as the order in which items are processed and so on.
@user1157751 Btw, I noticed your logic was target - current = index, It really should be target - current = value that has different index than current. Perhaps, that is causing an issue.
This example is wrong. When you run the code and print the returned value from twosum, you get (4,8) but the correct answer is (4,7).
@PaulCornelius One thing I noticed that I had wrong was that my answer did not give the one-indexed index pair. It's fixed now.
|
15

You want something along these lines:

#! python3

def two_sum(arr,targ):
    look_for = {}
    for n,x in enumerate(arr,1):
        try:
            return look_for[x], n
        except KeyError:
            look_for.setdefault(targ - x,n)

a = (2,7,1,15)
t = 9
print(two_sum(a,t))  # (1,2)

a = (-3,4,3,90)
t = 0
print(two_sum(a,t))  # (1,3)

Here you build the dictionary of values on an as-needed basis. The dictionary is keyed by the values you are seeking, and for each value you track the index of its first appearance. As soon as you come to a value that satisfies the problem, you're done. There is only one for loop.

The only other detail is to add 1 to each index to satisfy the ridiculous requirement that the indices be 1-based. Like that's going to teach you about Python programming.

Keys are added to the dictionary using the setdefault function, since if the key is already present you want to keep its value (the lowest index).

Improve this answer

2 Comments

a=(2,7,1,15) and t=9 then output will be (0,1)
I could not believe that this had escaped everyone's attention for seven years and fifteen upvotes, so I ran the program again just to make sure. It does indeed print (1, 2), so you must be doing something wrong. Are you forgetting to add 1 to the index?
14

I have just passed the following codes. To take advantage the dictionary and the notes that there is one and only one solution. To search the target-num in the saved lookup dictionary when saving the num in the lookup dictionary one by one. This method could save the space and also prevent the index overwriting when there are two same values in the nums. 

def twosum(self, nums, target):
    lookup = {}
    for cnt, num in enumerate(nums):
        if target - num in lookup:
            return lookup[target-num], cnt
        lookup[num] = cnt
Improve this answer

Comments

6

This answer uses zero-based indexing since that's the normal way to index, not one-based indexing. It also uses descriptive variable names, and is written for comprehension.

from typing import List, Tuple

def twosum_indices_linear(nums: List[int], target: int) -> Tuple[int, int]:
    numtoindexmap = {}
    for num1_index, num1 in enumerate(nums):
        num2 = target - num1
        try:
            num2_index = numtoindexmap[num2]
        except KeyError:
            numtoindexmap[num1] = num1_index  
            # Note: Use `numtoindexmap.setdefault(num1, num1_index)` instead for lowest num1_index.
        else:
            return tuple(sorted([num1_index, num2_index]))

Examples:

print(twosum_indices_linear([2, 7, 11, 15], 9))
(0, 1)

print(twosum_indices_linear([3, 3], 6))
(0, 1)

print(twosum_indices_linear([6, 7, 11, 15, 3, 6, 5, 3], 6))
(4, 7)

Credit: answer by joeg

Improve this answer

Comments

2

One-pass Hash Table

This can be done in one-pass. How Teo? Well, while it's iteratting and inserting elements into the hash, it should also look back to check if current element's complement already exists in the hash. If it exists, we have found a solution and return immediately.

Complexity:

Time complexity: O(n). We traverse the list containing n elements only once. Each look up in the table costs only O(1) time.

Space complexity: O(n). The extra space required depends on the number of items stored in the hash table, which stores at most n elements.

const nums = [1, 2, 4, 6, 7, 11, 15]
const target = 9


/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = (nums, target) => {
    const map = new Map()
    
    const l = nums.length
    for (var i = 0; i < l; i++) {
        const complement = target - nums[i]
        if (map.has(complement)) return [map.get(complement), i]
        
        map.set(nums[i], i)
    }
    
    throw new Error('No two sum solution')
}

const [a, b] = twoSum(nums, target)

const addendA = nums[a]
const addendB = nums[b]
console.log({addendA, addendB})

Improve this answer

1 Comment

I like this solution it's straight forward and indeed O(n)
1 
public static int[] twoSum1(int[] nums, int target) 
{
    int[] result = new int[2];
    Map<Integer, Integer> map = new HashMap<>();

 
    for(int i=0; i<nums.length; i++)
        map.put(nums[i],i);
    
    
    for(int i=0; i<nums.length; i++)
    {
        int index = i;
        int anotherValue = target-nums[index];
        
        if(map.get(anotherValue)!=null && map.get(anotherValue)!=i)
        {
            result[0] = index;
            result[1] = map.get(target-nums[index]);
            
            System.err.println("result[0]: " + result[0]);
            System.err.println("result[1]: " + result[1]);
            
            return result;
        }
    }        
    return result;
}
Improve this answer

1 Comment

Could you elaborate on the code?
1

Solution in JavaScript using Set

Time and Space Complexity = 0(n)

  function twoSum(nums, target) {
    const mySet = new Set()
  
    for (const element of nums) {
      const potentialMatch = target - element
      
      if (mySet.has(potentialMatch)) {
        return [potentialMatch, element]
      } else {
        mySet.add(element)
      }
    }
    
    return []
  }

Improve this answer

Comments

1

A JavaScript solution for this question:

/** 
1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1].
* */

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
function twoSum(nums, target) {
  const numsObjs = {}; // create nums obj with value as key and index as value eg: [2,7,11,15] => {2: 0, 7: 1, 11: 2, 15: 3}

  for (let i = 0; i < nums.length; i++) {
    const currentValue = nums[i];

    if (target - currentValue in numsObjs) {
      return [i, numsObjs[target - currentValue]];
    }
    numsObjs[nums[i]] = i;
  }

  return [-1, -1];
}

console.log(twoSum([3,7,3], 6))

Improve this answer

1 Comment

But this uses the same element twice. You have multiple references to nums
1

My one line solution:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        res=[[nums.index(val),nums[ind +1:].index(target-val)+ ind +1] for ind,val in enumerate(nums) if target -val in nums[ind +1:]]
        return res[0]
Improve this answer

1 Comment

You should add your explanation anyway (without waiting to be asked). That will make your answer far better, and more likely to attract upvotes.
0

Solution in JavaScript using nested for loop

Time Complexity = O(n^2)

Space Complexity = O(n)

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

test-cases

const twoSum = function(nums, target) {
    for(let i = 0;  i < nums.length; i++) {
        for (let j = i+1; j < nums.length; j++) {
            if(j === i) continue;
            if((nums[i] + nums[j]) === target) return [i, j];
        }
    }
};
Improve this answer

Comments

0

This answer is memory efficient as it uses list pop method, but takes longer time:

class Solution:   
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        
        while len(nums)>0:
            ind = len(nums)-1
            item = nums.pop()
            if target-item in nums:
                return [ind, nums.index(target-item)]
Improve this answer

Comments

0

I too struggled with multiple loops initially, finally slimming down to this:

def twoSum(self, nums: List[int], target: int) -> List[int]:
        
        d = dict()
        
        for i in range(0, len(nums), 1):
            
            if (d.get(target-nums[i]) != None):
                return [i, d.get(target-nums[i])]
            
            d[nums[i]] = i
Improve this answer

Comments

0

The answer of @Shashank was right but the results of this answer start from index 1 in the array so leetcode won't accept it. So here is the same solution with a simple change to start the array from index 0.

class Solution:
    def twoSum(self,nums, target):
        lookup = dict(((v, i) for i, v in enumerate(nums)))
        return next(( (i, lookup.get(target-v)) 
            for i, v in enumerate(nums) 
                if lookup.get(target-v, i) != i), None)
Improve this answer

Comments

0

I have an easy solution with python dictionary with time complexity o(n):

def two_sum1(arr,sum):
complement_dict = {}
for i in range(len(arr)):
    complement = sum - arr[i]
    if complement in complement_dict:
        return [complement_dict[complement], i]
    else:
        complement_dict[arr[i]] = i
Improve this answer

Comments

0

This is two pointer approach to solving this problem considering that the given array is not sorted:

def twoSum( nums, target):
    nums2 = sorted(nums)
    left = 0
    right = len(nums)-1
    while left <right:
        if nums2[left]+nums2[right] == target:
            x =nums.index(nums2[left])
            nums[x]=None
            
            y=nums.index(nums2[right])
            return [x,y]
        elif nums2[left]+nums2[right] < target:
            left+=1
            
            
            
        else:
            
            right -=1
            
           
    return []
print(twoSum([2,7,11,15],9))
Improve this answer

Comments

0

I like the solution by Paul Cornelius, but it fails timedome due to call to enumerate taking too long for large arrays. Better to skip the enumerate and just keep a count of index:

def findCombo(l,target):
    lookup = {}
    n = 0
    for x in l:
        try:
            return (n,lookup[x])
        except KeyError:            
            lookup.setdefault (target-x,n)
        n = n + 1
 
    return None

Note: Python timedome question uses index starting at 0

Improve this answer

Comments

0

This solution is time efficient (faster than 80% of the solutions on leetcode), but takes lots memory:

def twoSum(nums,target):
    k={value:index for index, value in enumerate(nums)} 
    # using dictionary comprehesion to create a dictionary that maps value to index 
    ans=[[j,k[target-x]] for j,x in enumerate(nums) if target-x in k] 
    # use list comprehension to create a set of answers; make sure no key error by using 'if target-x in k'
    ans=[x for x in ans if x[0] != x[1]] 
    # make sure the two indexes are not the same. E.g. twoSum([1,2,0],2) returns [[0,0],[0,1],[1,2],[2,1]]; and [0,0] is a wrong answer  
    return ans[0]
Improve this answer

Comments

0

This is my answer:

class Solution:
    def twoSum(self, nums, target):
        ls = []
        for i in range(0, len(nums)):
            item = target - nums[i]
            nums[i] = "done"
            if item in nums:
                if i != nums.index(item):
                    ls.append(i)
                    ls.append(nums.index(item))
                    return ls
Improve this answer

1 Comment

That fails in case where array is [3,2,4], and target =6. it returns [0,0] but expected [1,2]
0

I thinks the solutions above looks complex.

def twoSum(nums: List[int], target: int) -> List[int]:
   output = []
   for i in nums:
        for j in nums:
            if i + j == target and nums.index(i) != nums.index(j):
                output.append(nums.index(i))
                output.append(nums.index(j))
                return output

print(twoSum([2,7,11,15],9))
print(twoSum([3,2,4],6))

#OUTPUT

[0, 1]
[1, 2]
Improve this answer

1 Comment

There is no "above". If you need to refer to a different answer please refer by link, using the "Share" feature. Please explain your code, ideally as standalone.
-1 
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        r = []

        for i in range(len(nums)):
            temp = target - nums[i]
            if temp in r:
                return [i,nums.index(temp)]

            r.append(nums[i])
Improve this answer

5 Comments

Why should one use that? Please add some explanation to your answer such that others can learn from it
Suppose the list has [4,5,6,7] and the target is 11, the loop will check for all the values. Like in this example it starts with 4, so 11-4 = 7 which is present in the list. So the output would be the index of 4 and 7 i.e. [0,3]
Please add all such explanation to the answer, not to the comment section
Sorry Nico, I am new to this. Next time I will add the explanation to the answer. :-)
It's always good to find new people contributing to SO - don't hesitate to post answers to other questions, and of course post questions on your own!
-1 
nums = [2, 7, 11, 15]
target = 9
l = []
x = 1
length = len(nums) - 1
for i in nums:
    l.append(nums.index(i))
    if (target - i) in nums[x:]:
       l.append(length - nums[::-1].index(target - i))
       break
    else:
       l = []
       x = x + 1
print(l)

Please check the submission here: https://www.youtube.com/watch?v=PeJtMogExbo

Improve this answer

1 Comment

While this code snippet may solve the question, including an explanation really helps to improve the quality of your post. Remember that you are answering the question for readers in the future, and those people might not know the reasons for your code suggestion.
-1

This is my answer in C++:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_set<int>s;
        vector<int>ans;
    int j =0;
    for(int i=0;i<nums.size();i++)
    {
        int temp = target -nums[i];
        //int tempInd = i ;
        if(s.find(temp)!=s.end()){
            //cout<<i<<" ";
             ans.push_back(i) ;
            for(int j=0;j<nums.size();j++)
            {
                if(temp == nums[j]){
                    //cout<<j<<endl;
                    ans.push_back(j) ;
                break;
                }
            }
        }
        s.insert(nums[i]);

    }
        return ans ;
    }
};
Improve this answer

Comments

-1

This is my answer more fast in JavaScript:

const nums = [2,7,11,15];
const target = 9;
var twoSum = function(nums, target) {
    for (let i = 0; i < nums.length; i++) {
      for (let j = i+1; j < nums.length; j++) {
          if(nums[i]+nums[j] === target){
            console.log(i, j);
          }
      }
    }
};

twoSum(nums, target);
Improve this answer

1 Comment

it will take 0(n*n)

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.