งานของเราคือการเขียนฟังก์ชันที่แก้ปัญหาผลรวมสองผลได้ในเวลาเชิงเส้นมากที่สุด
ปัญหาสองผลรวม
จากอาร์เรย์ของจำนวนเต็ม เราต้องหาตัวเลขสองตัวเพื่อที่จะรวมกันเป็นตัวเลขเป้าหมายเฉพาะ
ฟังก์ชัน twoSum ควรส่งคืนดัชนีของตัวเลขสองตัวที่รวมกันเป็นเป้าหมาย และหากไม่มีองค์ประกอบสองตัวรวมกันเป็นเป้าหมาย ฟังก์ชันของเราควรส่งคืนอาร์เรย์ว่าง
การแก้ปัญหาในเวลา O(n)
เราจะใช้ hashmap เพื่อบันทึกรายการที่ปรากฏแล้วในแต่ละรอบเราจะตรวจสอบว่ามีองค์ประกอบใด ๆ ในแผนที่ซึ่งเมื่อเพิ่มไปยังองค์ประกอบปัจจุบันเพิ่มไปยังเป้าหมายหากมีเราจะส่งคืนอาร์เรย์ที่มี ดัชนีและหากเราผ่านลูปทั้งหมดโดยไม่ผ่านเงื่อนไขนี้ เราจะคืนค่าอาร์เรย์ที่ว่างเปล่า
ตัวอย่าง
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 ] []
