Two Sum Problem แบบ Linear Time ใน JavaScript

เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์ตัวเลขเป็นอาร์กิวเมนต์แรก และ target sum เป็นอาร์กิวเมนต์ที่สอง

ฟังก์ชันควรหาและคืน index ของสองตัวเลขจากอาร์เรย์ (ติดกันหรือไม่ติดกันก็ได้) ที่บวกกันได้ target sum (ถ้ามี) เงื่อนไขคือต้องทำใน linear time (หนึ่งรอบลูป)

เราจะเก็บตัวเลขที่วนลูปผ่านมาไว้ใน Map และถ้าพบคู่ที่รวมกันได้ target sum ให้คืนค่าทันที

ตัวอย่างโค้ด

const arr = [1, 3, 5, 7, 9, 11];
const target = 16;
const twoSum = function(arr, target) {
  const map = new Map();
  for(let i = 0; i < arr.length; i++) {
    let num = arr[i];
    if(map.get(num) === undefined){
      map.set(target-num, i)
    }else{
      return [map.get(num), i]
    };
  };
};
console.log(twoSum(arr, target));

ผลลัพธ์

ผลลัพธ์ที่แสดงในคอนโซลจะเป็นดังนี้:

[3, 4]