มือใหม่หัด Go: Two Sum

โจทย์ปัญหาที่พบได้บ่อยๆ สำหรับมือใหม่ คือ Two Sum จาก LeetCode นั่นเอง ในบทความนี้จะมาแสดงวิธีแก้โจทย์ด้วย Go กัน

Two Sum

• กำหนดให้ nums: array ของ int, target: int เป็น parameter ของ function เพื่อคืนค่าเป็น index ของสองตัวเลขที่ได้ผลรวมเท่ากับ target
• ในแต่ละ input จะมีผลลัพธ์แค่คำตอบเดียว จึงไม่จำเป็นต้องใช้เลขตัวเดิมมาคิด
• คืนค่าคำตอบไม่จำเป็นต้องเรียงลำดับ

Example:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]

Answer:

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

    for i, num := range nums {
        complement := target - num
        if _, ok := numMap[complement]; ok {
            return []int{numMap[complement], i}
        }
        numMap[num] = i
    }

    return nil
}

Explanation:

• numMap ตัวเปล่าใช้ในการเก็บค่าในรูปแบบ key: value ช่วยเก็บคำตอบ
• แตก index i and ค่า num ออกจาก array
• Iteration 1 : num = 2
  • complement := target - num ได้เป็น 7 จาก 9 - 2
  • เช็คว่ามี key 7 อยู่ใน numMap หรือไม่ โดยใช้ _, ok := numMap[complement]
    • ค่าแรกเป็น zero value ของ int = 0 แต่ไม่ได้ใช้จึงละไว้
    • ค่าที่สองเป็น false เพราะ numMap ยังว่างอยู่
  • จึงทำการ numMap[num] = i เพิ่มค่า map เป็น {2: 0}
• Iteration 2 num = 7
  • complement := target - num ได้เป็น 2 จาก 9 - 7
  • เช็คว่ามี key 2 อยู่ใน numMap หรือไม่ ซึ่งเป็น true
  • เข้าเงื่อนไขให้ return []int{numMap[complement], i} ออกมาเป็น [0, 1] คือ ตำแหน่ง index ของจำนวนที่รวมกันได้ target