LeetCode 001 - Two Sum

2026-04-02

easy　array

Given an array of integers nums and an integer target, return the indices i and j such that nums[i] + nums[j] == target and i != j.You may assume that every input has exactly one pair of indices i and j that satisfy the condition.Return the answer with the smaller index first.

Example 1:

Input:
nums = [3,4,5,6], target = 7

Output: [0,1]

Explanation: nums[0] + nums[1] == 7, so we return [0, 1].

Example 2:

Input: nums = [4,5,6], target = 10

Output: [0,2]

Example 3:

Input: nums = [5,5], target = 10

Output: [0,1]

Constraints:

• 2 <= nums.length <= 1000
• -10,000,000 <= nums[i] <= 10,000,000
• -10,000,000 <= target <= 10,000,000
• Only one valid answer exists.

Solution 1:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Approach: Iterative Search (Modified Brute Force)
        # 1. Find the smallest unprocessed number and calculate its complement (target - num).
        # 2. Scan the remaining elements in the array to find the complement.
        # 3. Repeat this process until a valid pair is found.
        # Time Complexity: O(N^2). In the worst case, we scan the array repeatedly for each element.
        # Space Complexity: O(N). The 'used_set' stores up to N visited indices.
        target_list = []
        smallest_index = 0
        used_set = set()
        while True:
            smallest_num = 100000000
            for i, num in enumerate(nums):
                if i not in used_set:
                    if smallest_num > num:
                        smallest_num = num
                        smallest_index = i

            next_target = target - smallest_num
            for i, num in enumerate(nums):
                if i == smallest_index:
                    continue
                if num == next_target:
                    target_list.append(smallest_index)
                    target_list.append(i)
                    break
            used_set.add(smallest_index)
            if target_list:
                break
        target_list = sorted(target_list)

        return target_list

Solution 2:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Approach: Two-Pass Hash Table
        # Pass 1: Build a hash map mapping each element's value to its index.
        # Pass 2: Iterate through the array to check if the complement (target - num) exists in the hash map.
        # Ensure the complement is not the current element itself to avoid reusing the same index.
        # Time Complexity: O(N). We traverse the list containing N elements exactly twice.
        # Space Complexity: O(N). The hash map stores at most N key-value pairs.
        hashmap = {}
        for i, num in enumerate(nums):
            hashmap[num] = i

        for i, num in enumerate(nums):
            difference = target - num
            if (difference in hashmap) and (i != hashmap[difference]):
                if i < hashmap[difference]:
                    return [i, hashmap[difference]]
                else:
                    return [hashmap[difference], i]

Solution 3:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Approach: One-Pass Hash Table
        # 1. Initialize an empty hash map to store numbers and their corresponding indices.
        # 2. Iterate through the array. For each element, calculate its complement (target - current number).
        # 3. Check if this complement already exists in the hash map.
        # 4. If it exists, we found the pair! Return the index of the complement and the current index.
        # 5. If it does not exist, add the current number and its index to the hash map for future lookups.
        # Note: Time complexity is O(N) and Space complexity is O(N).
        hashmap = {}
        for i, num in enumerate(nums):
            difference = target - num
            if difference in hashmap:
                return [hashmap[difference], i]
            hashmap[num] = i