บทความนี้สาธิตการหา triplet ทั้งหมด (unique) ในอาร์เรย์ที่ผลรวมเท่ากับ target number
ตัวอย่าง
arr = [4, 2, 0, 1, 2, 6, 8, 3, 2, 5], target = 8 output: [[2,2,4], [1,3,4], [0,2,6], [1,2,5]]
ตัวอย่างโค้ด
const arr = [4, 2, 0, 1, 2, 6, 8, 3, 2, 5];
const num = 8;
const tripletSum = (arr, num) => {
if (arr.length === 3) {
if (arr[0] + arr[1] + arr[2] === 0) {
return [[arr[0], arr[1], arr[2]]];
}
}
const results = [];
const hashMap = {};
for (var i = 0; i < arr.length; i++) {
for (var j = i + 1; j < arr.length; j++) {
for (var k = j + 1; k < arr.length; k++) {
if (arr[i] + arr[j] + arr[k] === num) {
if (!hashMap[arr[i] * arr[j] * arr[k]]) {
results.push([arr[i], arr[j], arr[k]]);
results[results.length - 1].sort();
hashMap[arr[i] * arr[j] * arr[k]] = true;
}
}
}
}
}
return results;
};
console.log(tripletSum(arr, num));
ผลลัพธ์
[[2, 2, 4], [1, 3, 4], [0, 2, 6], [1, 2, 5]]
คำอธิบาย
ใช้ 3 nested loops (O(n^3)) หา triplet ทุกคู่ ใช้ hashMap ป้องกัน duplicate โดยใช้ product เป็น key (อาจมี collision ถ้าตัวเลขต่างกันแต่ product เท่ากัน)
วิธีที่ดีกว่า: เรียงอาร์เรย์ + two pointers O(n^2)
