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 complexity | O(n^2) |
| Space complexity | O(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 complexity | O(n) |
| Space complexity | O(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.