1. Two Sum

---

Description

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

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

You can return the answer in any order.

 

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

 

Constraints:

    2 <= nums.length <= 104
    -109 <= nums[i] <= 109
    -109 <= target <= 109
    Only one valid answer exists.

 
Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

---

Code

func twoSum(nums []int, target int) []int {
    	if len(nums) == 2 {
		return []int{0, 1}
	}

	start_x := 0
	for {
		for start_y := start_x + 1; start_y < len(nums); start_y++ {
			if nums[start_x]+nums[start_y] == target {
				return []int{start_x, start_y}
			}
		}
		start_x++
	}
}

 

주어진 함수 twoSum은 주어진 배열 nums의 요소를 하나씩 탐색하면서 두 요소의 합이 주어진 target과 일치하는지 확인합니다. 이러한 경우, 최악의 경우에는 모든 요소를 한 번씩만 확인하기 때문에 시간 복잡도는 O(n)입니다. 하지만 중첩된 루프가 없으므로, O(n)의 성능을 가집니다.

---

func twoSum(nums []int, target int) []int {
	value_index := make(map[int]int)

	for index, value := range nums {
		diff := target - value

		if i, ok := value_index[diff]; ok {
			return []int{i, index}
		} else {
			value_index[value] = index
		}
	}

	return nil
}

 

이 코드는 효율적인 해시 맵을 사용하여 두 수의 합을 찾는 것으로 O(n) 시간 복잡도를 갖습니다. 주어진 배열을 한 번만 반복하면서 각 요소를 해시 맵에 저장하고, 동시에 타겟과의 차이가 이미 해시 맵에 있는지 확인합니다. 만약 있다면, 해당 요소의 인덱스와 현재 인덱스를 반환합니다. 이 방법은 중첩된 루프가 없으므로 O(n) 성능을 유지합니다.