หน้าที่ของเราคือเขียนฟังก์ชันที่แก้ปัญหา two-sum ในเวลาเชิงเส้นสูงสุด
ปัญหา Two Sum
ได้รับอาร์เรย์ของจำนวนเต็ม เราต้องหาสองตัวเลขที่บวกกันได้เท่ากับเป้าหมายเฉพาะ
ฟังก์ชัน twoSum ควรคืนค่าดัชนีของสองตัวเลขที่บวกกันได้เป้าหมาย และถ้าไม่มีสององค์ประกอบไหนบวกกันได้เป้าหมาย ฟังก์ชันควรคืนค่าอาร์เรย์ว่าง
แก้ปัญหาในเวลา O(n)
เราจะใช้ hashmap เพื่อบันทึกไอเท็มที่ปรากฏแล้ว ในแต่ละรอบ เราจะตรวจสอบว่ามีองค์ประกอบใน map ไหนที่บวกกับองค์ประกอบปัจจุบันได้เป้าหมาย ถ้ามี เราจะคืนค่าอาร์เรย์ที่มีดัชนีของพวกเขา และถ้าเราได้ลูปทั้งหมดโดยไม่ตรงเงื่อนไข เราจะคืนค่าอาร์เรย์ว่าง
ตัวอย่าง
const arr = [2, 5, 7, 8, 1, 3, 6, 9, 4]; const sum = 10; const twoSum = (arr, sum) => { const map = {}; for(let i = 0; i < arr.length; i++){ const el = sum - arr[i]; if(map[el]){ return [map[el], i]; }; map[arr[i]] = i; }; return []; }; console.log(twoSum(arr, sum)); console.log(twoSum(arr, 12)); console.log(twoSum(arr, 13)); console.log(twoSum(arr, 14)); console.log(twoSum(arr, 24));ผลลัพธ์
ผลลัพธ์ในคอนโซลจะเป็นดังนี้
[ 2, 5 ] [ 1, 2 ] [ 1, 3 ] [ 3, 6 ] []
