[golang] LeetCode #1. Two Sum

개요

이전에 작성한 글에서 해결 못했지만, 다시 풀어보고 해결이 되었으므로, 여기에 해결법을 남긴다.
이전에 작성한 글(미해결)

1. 문제

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example 1:

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

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

해설

integer배열이 주어지면, 더해서 target 이 되는 두 인덱스를 반환한다.

각 input 값은 단 하나의 답만 가진다고 가정하며, 같은 요소를 사용해서는 안된다.

2. 접근

// 0 과 1, 2, 끝을 더한다.
// 1 과 2, 끝을 더한다. 
// 2 과 끝을 더한다. 
// 끝 아무것도 하지 않는다. 

// for 로 반복한다. i 는 0 부터 len까지
// nums[i] 와 j 는 i+1 부터 len까지이며, nums[i] + nums[j] 를 더한다. 
// target과 일치하면 동작 완료

3. 내가 작성한 답

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

4. 다른 유저의 답안

맵을 활용한 방법

타겟에서 각 값을 뺀 값을 키로 하는 맵을 만들어서,
해당 키가 존재하면 그 키를 만들때 뺀 값과 쌍이 되므로 그 때의 인덱스 배열을 반환하는 똑똑한 방법

func twoSum(nums []int, target int) []int {
    m := make(map[int]int)
    for i, n := range nums {
        _, prs := m[n]
        if prs {
            return []int{m[n], i}
        } else {
            m[target-n] = i
        }
    }
    return nil
}

이해하고 감탄했다.
열쇠는 m[target-n] = i 이 부분

또 다른 방법

발상은 위 유저와 비슷하지만, 작성법이 약간 달라서 참고로 가져왔다.

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

5. 추가로 공부한 내용

• 맵의 작동 방식 Go maps in action
• 슬라이스 내부 작동 방식 Go Slices: usage and internals