Two Sum LeetCode Solution

Last updated on January 12th, 2025 at 03:25 am

Here, we see Two Sum LeetCode problem. This Leetcode problem is solved in many programming languages, such as C++, Java, JavaScript, Python, etc., with different approaches.

List of all LeetCode Solution

Topics

Array, Hash-Table

Companies

Adobe, Airbnb, Amazon, Apple, Bloomberg, Dropbox, Facebook, LinkedIn, Microsoft, Uber, Yahoo, Yelp

Level of Question
Two Sum LeetCode Solution

Two Sum LeetCode Solution

1. 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]

2. Coding Pattern Used in Solution

The coding pattern used in the provided code is “Hash Table Lookup“. It is a common and efficient approach for solving problems involving finding complements, duplicates, or relationships between elements in an array.

3. How the Code Works

  1. Java and Python Code:
    • These implementations use a brute-force approach.
    • They iterate through all pairs of elements in the array using two nested loops.
    • For each pair, they check if the sum of the two numbers equals the target.
    • If a match is found, the indices of the two numbers are returned.
  2. C++ and JavaScript Code:
    • These implementations use a hash table (or map) for efficient lookups.
    • As the array is traversed, the code calculates the “complement” (i.e., the number needed to reach the target when added to the current number).
    • If the complement is already in the hash table, the indices of the current number and the complement are returned.
    • Otherwise, the current number and its index are added to the hash table for future lookups.

4. Code Implementation in Different Languages

4.1 Two Sum C++

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;
    }
};

4.2 Two Sum Java

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;
    }
}

4.3 Two Sum JavaScript

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);
    }
};

4.4 Two Sum Python

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]

5. Time and Space Complexity

Coding PatternTime ComplexitySpace Complexity
JavaBrute ForceO(n²)O(1)
PythonBrute ForceO(n²)O(1)
C++Hash TableO(n)O(n)
JavaScriptHash TableO(n)O(n)
  • The brute-force approach (Java and Python) is simple but inefficient for large arrays due to its quadratic time complexity.
  • The hash table approach (C++ and JavaScript) is more efficient, with linear time complexity, but it requires additional space for the hash table.
  • The choice of approach depends on the constraints of the problem (e.g., array size, memory limitations).
Scroll to Top