Difficulty: Easy · LeetCode 1

Problem

Given an array of integers nums and an integer target, return indices of the two numbers that add up to target. Exactly one solution exists. You may not use the same element twice.

Examples

Input

nums: int[], target: int
2 ≤ n ≤ 10⁴

Output

int[2] — indices [i, j] where nums[i]+nums[j]=target

Constraints

2 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i], target ≤ 10⁹
Only one valid answer exists

Understanding the problem

For each element x, we need target - x. Brute force checks all pairs O(n²). Optimization: store each element in a map as we scan, look up the complement in O(1).

Intuition

For each element x, we need target - x. Store visited elements in {value: index} map. Check if the complement exists before inserting current element.

Approach

Init empty map seen = {value: index}.
For each index i: compute complement = target - nums[i].
If complement in seen → return [seen[complement], i].
Else store seen[nums[i]] = i.

Naive Solution — O(n²)

Check all pairs (i, j) with i < j.

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

C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        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 {};
    }
};

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[i]+nums[j]==target) return new int[]{i,j};
        return new int[]{};
    }
}

JavaScript

var twoSum = function(nums, target) {
    for (let i = 0; i < nums.length; i++)
        for (let j = i+1; j < nums.length; j++)
            if (nums[i]+nums[j]===target) return [i,j];
};

Time: O(n²) · Space: O(1)

Optimized Code — One-pass HashMap

Python

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        seen = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in seen:
                return [seen[complement], i]
            seen[num] = i

C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> seen;
        for (int i = 0; i < nums.size(); i++) {
            int comp = target - nums[i];
            if (seen.count(comp)) return {seen[comp], i};
            seen[nums[i]] = i;
        }
        return {};
    }
};

Java

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> seen = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int comp = target - nums[i];
            if (seen.containsKey(comp)) return new int[]{seen.get(comp),i};
            seen.put(nums[i], i);
        }
        return new int[]{};
    }
}

JavaScript

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

Time: O(n) · Space: O(n)

Variants

Takeaway

Pattern: Complement Lookup via HashMap — Store visited elements, check complement on each step. Canonical HashMap-in-arrays pattern. Generalizes to 3Sum (sort + fix + two-ptr) and 4Sum.