Last updated on July 8th, 2024 at 02:25 am

Here, We see Two Sum LeetCode problem Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.

List of all LeetCode Solution

Two Sum LeetCode Solution

Problem Statement

Given an array of integer 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 3:
Input: nums = [3,3], target = 6
Output: [0,1]

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> cache;
        vector<int> answer;
        
        for (size_t i = 0; i < nums.size(); ++i)
        {
            int needed_num = target - nums[i];
            
            if (cache.find(needed_num) != cache.end())
            {
                // We found it
                answer.push_back(cache[needed_num]);
                answer.push_back(i);
                return answer;
            }
            else
            {
                // Didn't find it
                cache.insert(make_pair(nums[i], i));
            }
        }
        return answer;
    }
};

1.1 Explanation

1. unordered_map<int, int> cache; – This initializes an unordered map to store the numbers encountered and their indices.
2. vector<int> answer; – This vector will store the indices of the two numbers that sum up to the target.
3. The for the loop iterates over the nums array.
4. needed_num is calculated as target – nums[i].
5. If needed_num is found in cache, the indices are added to answer and returned.
6. If needed_num is not found, the current number and its index are added to cache.

1.2 Time Complexity

• Each element is processed once, and the unordered_map operations (insertion and lookup) are on average O(1).
• Therefore, the time complexity is O(n).

1.3 Space Complexity

• The space complexity is O(n) because in the worst case, we could be storing all elements in the unordered_map.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] == target - nums[i]) {
                    return new int[] { i, j };
                }
            }
        }
        return null;
    }
}

2.1 Explanation

1. Two nested loops iterate over the array.
2. The outer loop runs from the first element to the second last element.
3. The inner loop runs from the current element of the outer loop to the last element.
4. If the sum of the current element and the inner loop element equals the target, their indices are returned.

2.2 Time Complexity

• The time complexity is O(n²) because of the nested loops.

2.3 Space Complexity

• The space complexity is O(1) as no extra space is used other than the variables for indices.

var twoSum = function(nums, target) {
    let map = new Map;
    for (var i = 0; i < nums.length; i++) {
        let complement = target - nums[i];
        if (map.has(complement)) {
            return [map.get(complement), i]
        }
        map.set(nums[i], i);
    }
};

3.1 Explanation

1. let map = new Map; initializes a map to store the numbers and their indices.
2. The for loop iterates over the nums array.
3. complement is calculated as target – nums[i].
4. If complement is found in map, the indices are returned.
5. If complement is not found, the current number and its index are added to map.

3.2 Time Complexity

• Each element is processed once, and the Map operations (insertion and lookup) are on average O(1).
• Therefore, the time complexity is O(n).

3.3 Space Complexity

• The space complexity is O(n) because in the worst case, we could be storing all elements in the Map.

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[j] == target - nums[i]:
                    return [i, j]

4.1 Explanation

1. Two nested loops iterate over the array.
2. The outer loop runs from the first element to the second last element.
3. The inner loop runs from the current element of the outer loop to the last element.
4. If the sum of the current element and the inner loop element equals the target, their indices are returned.

4.2 Time Complexity

• The time complexity is O(n²) because of the nested loops.

4.3 Space Complexity

• The space complexity is O(1) as no extra space is used other than the variables for indices.