บทความนี้สาธิต two-pointer technique หาคู่ตัวเลขใน sorted array ที่ผลรวมเท่ากับ target ใช้เวลา O(n) และ space O(1)
ตัวอย่าง
arr = [4, 6, 8, 9, 11, 12, 18, 21], target = 27 output: [6, 21]
ตัวอย่างโค้ด
const arr = [4, 6, 8, 9, 11, 12, 18, 21];
const num = 27;
const findElements = (arr = [], target) => {
let left = 0;
let right = arr.length - 1;
let res = [];
while (left < right) {
let leftElement = arr[left];
let rightElement = arr[right];
if (leftElement + rightElement === target) {
res.push(arr[left]);
res.push(arr[right]);
break;
} else if (leftElement + rightElement > target) {
right--;
} else {
left++;
}
}
return res;
};
console.log(findElements(arr, num));
ผลลัพธ์
[6, 21]
คำอธิบาย
left เริ่มหน้า, right เริ่มท้าย หาก sum > target -> right-- (ลดค่า) หาก sum < target -> left++ (เพิ่มค่า)
ต้องการ array ที่ sorted ascending
