LeetCode의 Two Sum Problem'-Golang-php.cn

LeetCode의 Two Sum Problem'

Barbara Streisand

풀어 주다： 2024-11-16 15:30:03

원래의

163명이 탐색했습니다.

Two Sum Problem’ on LeetCode

문제 설명
정수 배열 nums와 정수 목표가 주어지면 목표에 합산되는 두 숫자의 인덱스를 반환합니다.

Go 함수 서명:
func twoSum(nums []int, target int) []int
예시 1:
입력: 숫자 = [2,7,11,15], 대상 = 9
출력: [0,1]
설명: nums[0] nums[1] == 9이므로 [0, 1]을 반환합니다.
예시 2:

입력: 숫자 = [3,2,4], 대상 = 6
출력: [1,2]
예시 3:

입력: 숫자 = [3,3], 대상 = 6
출력: [0,1]
솔루션 1: 무차별 접근 방식

해결책 1: 무차별 접근 방식(중첩 루프)
이 접근 방식에서는 각 요소 쌍을 확인하여 해당 요소의 합이 목표에 도달하는지 확인합니다. 여기에는 두 개의 중첩 루프를 사용하여 배열을 반복하는 작업이 포함됩니다.

코드

func twoSum(nums []int, target int) []int {
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i] + nums[j] == target {
                return []int{i, j}
            }
        }
    }
    return nil
}

로그인 후 복사

복잡성 분석

해결책 2: 2단계 해시 테이블
이 솔루션은 해시 맵을 사용하여 첫 번째 단계에서 각 요소의 값과 인덱스를 저장함으로써 무차별 접근 방식을 개선합니다. 두 번째 패스에서는 해시 맵에 보완(즉, 대상 - 숫자)이 존재하는지 확인합니다.

코드

func twoSum(nums []int, target int) []int {
    numMap := make(map[int]int)
    // First pass: populate the map with each element's index
    for i, num := range nums {
        numMap[num] = i
    }
    // Second pass: check for the complement
    for i, num := range nums {
        if j, ok := numMap[target - num]; ok && i != j {
            return []int{i, j}
        }
    }
    return nil
}

로그인 후 복사

해결책 3: 원패스 해시 테이블(최적 솔루션)

이 접근 방식은 삽입과 조회를 단일 패스로 결합합니다. 배열을 반복하면서 다음이 수행됩니다.
해시 맵에 보완물(즉, target - num)이 있는지 확인하세요.
보체가 발견되면 인덱스를 반환합니다.
그렇지 않은 경우 향후 조회를 위해 현재 요소와 해당 인덱스를 해시 맵에 추가하세요.
코드

func twoSum(nums []int, target int) []int {
    numMap := make(map[int]int)
    for i, num := range nums {
        if j, ok := numMap[target - num]; ok {
            return []int{j, i}
        }
        numMap[num] = i
    }
    return nil
}

로그인 후 복사

복잡성 분석