1. Two Sum

Đề bài

Cho một mảng số nguyên nums và một giá trị mục tiêu target. Hãy trả về chỉ số của hai phần tử sao cho tổng của chúng đúng bằng target.

Bạn có thể giả định mỗi đầu vào luôn có đúng một nghiệm, và không được dùng lại cùng một phần tử.

Ví dụ:

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

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

Tóm tắt đề

Tìm trong mảng 2 số có tổng bằng giá trị cho trước, rồi trả về chỉ số của chúng trong mảng.

Ý tưởng

Cách tối ưu cho bài này có độ phức tạp thời gian $O(n)$.

Duyệt mảng từ trái sang phải. Với mỗi phần tử nums[i], ta tính “nửa còn lại” another = target - nums[i] rồi tra trong map xem đã từng gặp another chưa:

• Nếu đã có: trả về ngay cặp chỉ số.
• Nếu chưa có: lưu nums[i] -> i vào map để lát nữa gặp “nửa còn lại” thì lấy ra.

Code

package leetcode

func twoSum(nums []int, target int) []int {
	m := make(map[int]int)
	for i := 0; i < len(nums); i++ {
		another := target - nums[i]
		if _, ok := m[another]; ok {
			return []int{m[another], i}
		}
		m[nums[i]] = i
	}
	return nil
}

---