เราต้องเขียนฟังก์ชัน พูด threeSum() ที่รับอาร์เรย์ของ Numbers และ targetsum จะตรวจสอบว่ามีตัวเลขสามตัวในอาร์เรย์ที่บวกกับผลรวมเป้าหมายหรือไม่ หากมีตัวเลขสามตัวดังกล่าวในอาร์เรย์ ก็ควรส่งคืนดัชนีในอาร์เรย์มิฉะนั้นควรคืนค่า -1
แนวทาง
วิธีการนั้นง่าย ก่อนอื่นเราจะเขียนฟังก์ชัน twoSum() ซึ่งรับอาร์เรย์และผลรวมของเป้าหมายและใช้เวลาเชิงเส้นและช่องว่างเพื่อส่งคืนดัชนีของตัวเลขสองตัวที่รวมกันเป็นยอดรวมของเป้าหมาย มิฉะนั้น -1
จากนั้นเราเขียนฟังก์ชันจริง threeSum() ที่วนซ้ำแต่ละองค์ประกอบในอาร์เรย์เพื่อค้นหาดัชนีขององค์ประกอบที่สาม ซึ่งเมื่อเพิ่มลงในตัวเลข twoSum() สามารถเพิ่มได้ถึงเป้าหมายจริง
ดังนั้น เช่นนี้ เราสามารถหาสามองค์ประกอบในเวลา O(N^2) มาเขียนโค้ดสำหรับสิ่งนี้กัน −
ตัวอย่าง
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
