Two Sum

1. Problem Description

Given an integer array, find two numbers in the array whose sum equals the target value. The twoSum function should return the indices of these two numbers (index1, index2), with index1 < index2. Note: indices start from 1. Assume there is exactly one solution in the given array. For example: Given the array {20, 70, 110, 150} and target value 90, output index1=1, index2=2.

2. Approach

Compared with Two Numbers Whose Sum Is S, this array is not sorted.

1. Approach 1
   • Brute force
   • Fix one number and scan for the other number
2. Approach 2
   • Traverse once and put the elements into a set
   • Traverse again and check whether the other number exists in the map

3. Implementation

3.1. Brute Force

// Time: O(N²)
// Space: O(1)
func twoSum(numbers []int, target int) []int {
	if len(numbers) == 0 {
		return nil
	}

	res := make([]int, 0)
	for i := 0; i < len(numbers); i++ {
		for j := i + 1; j < len(numbers); j++ {
			if numbers[i]+numbers[j] == target {
				res = append(res, i+1, j+1)
				return res
			}

		}
	}

	return res

}

3.2. map

// Time: O(N)
// Space: O(N)
func twoSum2(numbers []int, target int) []int {
	if len(numbers) == 0 {
		return nil
	}

	res := make([]int, 0)

	m := make(map[int]int, 0)
	for i := 0; i < len(numbers); i++ {
		m[numbers[i]] = i
	}

	for i := 0; i < len(numbers); i++ {
		j, ok := m[target-numbers[i]]
		if j == i {
			continue
		}
		if ok {
			res = append(res, i+1, j+1)
			return res
		}
	}

	return res

}

4. References

• Two Sum - NowCoder
• Two Sum - LeetCode