Leetcode - 1. Two Sum

Easy

Dec 22, 2025

#hashmap

#math

1. 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 3:

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

Constraints:

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

**Follow-up:**Can you come up with an algorithm that is less than O(n2) time complexity?

Notes

Intuition

The key insight is that for any number in the array, we need to check if its complement (target - curr) exists elsewhere. Rather than using a nested loop to search for each complement, we can use a hashmap to achieve constant-time lookups.

Implementation

First, populate a hashmap with all numbers and their indices, allowing overwrites since duplicates won't be part of the answer. Then iterate through the array again, computing each number's complement and checking if it exists in the map. If found, return the pair of indices.

Edge-cases

The main edge case is ensuring that the complement isn't the number itself. Always verify that map[complement] != i before returning—this prevents using the same element twice.

Time: O(n) — two passes through the array
Space: O(n) — hashmap stores up to n elements

Complexity

Solution

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        map = {}
        for i in range(len(nums)):
            map[nums[i]] = i

        for i in range(len(nums)):
            curr = nums[i]
            complement = target - curr
            if complement in map and map[complement] != i:
                return [map[complement], i]

        print("should not get here, check testcases")
        return [0, 0]
        



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()