Skip to content

LeetCode: 1-Two Sum Solution

Last Updated on 2022-09-13 by Clay

Problem

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.

Example:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Solution

The problem is one of LeetCode's most classic question: because it is the first problem on the problem page!


Brute Force

Time complexityO(n^2)
Space complexityO(1)

Most of the methods that come to mind are to use two for-loops to traverse all combinations.

However, this method is time-consuming.

C++ Sample Code

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // Find
        for (int i=0; i<nums.size(); ++i) {
            for (int j=i+1; j<nums.size(); ++j) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        
        return {};
    }
};



Python Sample Code

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return (i, j)



HashMap

Time complexityO(n)
Space complexityO(n)

Another optimized solution is, we build a hash table or new array, check the number of nums one by one. If the current number is not in hash table (or array), we store the target-nums[i] into hash table;

If the current value is exactly equal to a certain value stored before, it means the current value and the original value of the stored value is the ANSWER!

C++ Sample Code

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> losses;
        
        for(int i=0; i<nums.size(); i++) {            
            if (losses.find(nums[i]) != losses.end()) {
                return {losses[nums[i]], i};
            }
            else {
                losses[target-nums[i]] = i;
            }
        }
        
        return {};
    }
}; 



Python Sample Code

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        losses = dict()
        
        for i in range(len(nums)):
            if nums[i] in losses:
                return (losses[nums[i]], i)
            else:
                losses[target-nums[i]] = i


In this way, the answer is solved with only one round of the loop.


References

Leave a Reply