โจทย์
เขียนฟังก์ชัน threeSum() ที่รับ array ของตัวเลขและ target sum ตรวจสอบว่ามี 3 ตัวเลขใน array ที่บวกกันได้ target sum หรือไม่ ถ้ามีคืนค่า indices ของทั้ง 3 ไม่มีคืน -1
แนวทาง
1. เขียนฟังก์ชัน twoSum() หา 2 ตัวเลขที่บวกกันได้ target (O(N) time/space)
2. ใช้ threeSum() วนลูปหา element ตัวที่ 3 ซึ่งเมื่อรวมกับผลลัพธ์จาก twoSum จะได้ target จริง
3. Complexity รวม O(N²)
ตัวอย่างโค้ด
const arr = [1,2,3,4,5,6,7,8];
const twoSum = (arr, sum) => {
const map = {};
for(let i = 0; i < arr.length; i++){
if(map[sum-arr[i]]){
return [map[sum-arr[i]], i];
};
map[arr[i]] = i;
};
return -1;
};
const threeSum = (arr, sum) => {
for(let i = 0; i < arr.length; i++){
const indices = twoSum(arr, sum-arr[i]);
if(indices !== -1 && !indices.includes(i)){
return [i, ...indices];
};
};
return -1;
};
console.log(threeSum(arr, 9));
console.log(threeSum(arr, 8));
console.log(threeSum(arr, 13));
console.log(threeSum(arr, 23));
ผลลัพธ์
[ 0, 2, 4 ] [ 0, 2, 3 ] [ 0, 4, 6 ] -1
คำอธิบาย
ใช้ hash map ใน twoSum เพื่อหาคู่ที่รวมกันได้ sum ใน O(1) แล้ววนลูปหาตัวที่ 3 ทำให้ได้ O(N²) ทั้งหมด ซึ่งดีกว่า brute force O(N³)
