Solutions

# Use hash map for O(1) lookups, preserving indices without sorting.
# hash-map,arrays
# Optimized, O(n) time, O(n) space
def twoSum(nums: list[int], target: int) -> list[int]:
    seen = {}
    for i, num in enumerate(nums):
        if target - num in seen:
            return [seen[target - num], i]
        seen[num] = i

# Sorting and two pointers, O(nlogn) time, O(1) space
def twoSum(nums: list[int], target: int) -> list[int]:
    A = []
    for i, num in enumerate(nums):
        A.append([num, i])

    A.sort()
    i, j = 0, len(nums) - 1
    while i < j:
        cur = A[i][0] + A[j][0]
        if cur == target:
            return [A[i][1], A[j][1]]
        elif cur < target:
            i += 1
        else:
            j -= 1
    return []

# Brute force, O(n^2) time, O(1) space
def twoSum(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]
    return []