Two Sum
Two Sum:
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 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 2:
Input: nums = [3,3], target = 6
Output: [0,1]
Constraints:
2 <= nums.length <= 10^4-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9- Only one valid answer exists.
Try this Problem on your own or check similar problems:
Solution:
- Java
- JavaScript
- Python
- C++
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; ++i){
if (map.containsKey(target - nums[i])){
return new int[]{map.get(target - nums[i]), i};
}
map.put(nums[i], i);
}
return new int[]{0,0};
}
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
let map = new Map();
for (let i = 0; i < nums.length; ++i) {
if (map.has(target - nums[i])) {
return [map.get(target - nums[i]), i];
}
map.set(nums[i], i);
}
return [0, 0];
};
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
map = {}
for i in range(len(nums)):
if target - nums[i] in map:
return [map[target - nums[i]], i]
map[nums[i]] = i
return [0, 0]
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
std::unordered_map<int, int> map;
for (int i = 0; i < nums.size(); ++i) {
if (map.count(target - nums[i])) {
return { map[target - nums[i]], i };
}
map[nums[i]] = i;
}
return { 0, 0 };
}
};
Time/Space Complexity:
- Time Complexity: O(n)
- Space Complexity: O(n)
Explanation:
It's trivial to write O(n^2) solution by checking if sum of any pair in input array sums up to the target, but to reduce time complexity we allocate a helper hashmap that enables us O(1) (amortized) get operation. Each iteration we check if there is an element already in hashmap that together with current element adds up to the target (we do that by subtracting current element from the target map.containsKey(target - nums[i])). If not, we just store the current element in the hasmap hoping we will find its pair in the rest of array (by problem statement we will, since there is a guarantee exactly one solution exists). Notice that we got a unsorted input array, you could make a statement that if array was sorted you would use two pointers approach, where you would place one pointer at the start of sorted array and the other one in the end. If their sum is equal to target you would just return the indices of those two elements, otherwise we would move the start to the right if the sum is less than target or move the right pointer to the left if the sum is larger than target. You can check Squares of a Sorted Array solution to see this approach in action.