Two Sum Easy ​

Question ​

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.

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

Input: nums = [3,2,4], target = 6
Output: [1,2]

Input: nums = [3,3], target = 6
Output: [0,1]

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109

Only one valid answer exists.

Solution ​

def two_sum(nums, target):
    num_index_map = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_index_map:
            return [num_index_map[complement], i]
        num_index_map[num] = i

import java.util.HashMap;

public class TwoSum {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> numIndexMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (numIndexMap.containsKey(complement)) {
                return new int[]{numIndexMap.get(complement), i};
            }
            numIndexMap.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two elements add up to the target.");
    }
}

function twoSum(nums, target) {
    const numIndexMap = {};
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (numIndexMap.hasOwnProperty(complement)) {
            return [numIndexMap[complement], i];
        }
        numIndexMap[nums[i]] = i;
    }
    throw new Error("No two elements add up to the target.");
}

Notes ​

The goal of the given problem is to find two numbers in the input array nums that add up to the given target. We are required to return the indices of these two numbers.

The solution uses a hash map (dictionary) to efficiently keep track of elements seen so far while iterating through the array. For each element num at index i in the nums array, it calculates the complement complement = target - num. If the complement is present in the hash map, it means we have found the pair of elements that sum up to the target, and their indices are returned. If the complement is not in the hash map, we add the current element and its index to the hash map for future reference.

Time Complexity: ​

The time complexity of the provided solution is O(n), where n is the number of elements in the nums array. The reason for this is that we iterate through the array once, and for each element, we perform constant time operations like checking the hash map and inserting elements into it. The lookup and insertion operations in a hash map generally take O(1) time on average.

Space Complexity: ​

The space complexity of the provided solution is O(n) as well. In the worst case, we may need to store all the elements of the nums array in the hash map. This would happen when there are no two elements that add up to the target, and we end up storing all elements in the hash map before we determine that there is no solution. Therefore, the space complexity is linear in the number of elements in the nums array.

Overall, this solution efficiently solves the problem in linear time and space complexity by using a hash map to keep track of elements seen so far while iterating through the array. This approach allows us to find the pair of elements that sum up to the target in a single pass through the array.