What is the best way to solve Two Sum?

The optimized O(n) approach using Arrays & Hashing patterns is generally preferred.

상위 150개 인터뷰쉬움

투섬

'Two Sum' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

쉬움

정수 배열 nums과 정수 target이 주어지면 두 숫자의 합이 target가 되도록 두 숫자의 인덱스를 반환합니다.

각 입력에는 정확히 하나의 솔루션이 있다고 가정할 수 있으며 동일한 요소를 두 번 사용할 수 없습니다.

어떤 순서로든 답변을 반환할 수 있습니다.

twoSum(nums: List[int], target: int) -> List[int] 함수를 작성하세요.

제약

•2 <= len(nums) <= 10^4
•-10^9 <= nums[i] <= 10^9
•-10^9 <= target <= 10^9
•Only one valid answer exists

예

Example 1

Input

nums = [2, 7, 11, 15], target = 9

Output

[0, 1]

Explanation

nums[0] + nums[1] = 2 + 7 = 9, so we return [0, 1].

Example 2

Input

nums = [3, 2, 4], target = 6

Output

[1, 2]

Explanation

nums[1] + nums[2] = 2 + 4 = 6, so we return [1, 2].

Example 3

Input

nums = [3, 3], target = 6

Output

[0, 1]

Explanation

nums[0] + nums[1] = 3 + 3 = 6, so we return [0, 1].

Need a Hint?

세트나 힙과 같은 배열 및 해싱 관련 데이터 구조를 사용해 보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

배열 및 해싱 접근 방식의 논리를 설명하세요.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(n)•Space: O(n)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

def two_sum_opt(nums, target):
    prevMap = {} # val : index
    for i, n in enumerate(nums):
        diff = target - n
        if diff in prevMap:
            return [prevMap[diff], i]
        prevMap[n] = i
    return []

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

def two_sum_brute(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []