โปรแกรม Java หาคู่ที่ใกล้เคียงที่สุดจาก Sorted Arrays 2 อัน

โจทย์: 2 Sorted Arrays หาคู่ (a, b) ที่ |a + b - target| น้อยที่สุด

Two Pointers Technique (O(n + m))

Pointer ซ้าย (i) เริ่ม arr1[0], Pointer ขวา (j) เริ่ม arr2[m-1]
ผลรวม > target → j-- (ลดค่า)
ผลรวม < target → i++ (เพิ่มค่า)

ตัวอย่างโค้ด (แก้ไข bug ใน original)

public class Demo {
    static void closestPair(int[] arr1, int[] arr2, int target) {
        int i = 0;
        int j = arr2.length - 1;
        int minDiff = Integer.MAX_VALUE;
        int bestI = 0, bestJ = 0;
        
        while (i < arr1.length && j >= 0) {
            int sum = arr1[i] + arr2[j];
            int diff = Math.abs(sum - target);
            
            if (diff < minDiff) {
                minDiff = diff;
                bestI = i;
                bestJ = j;
            }
            
            if (sum > target) {
                j--;
            } else if (sum < target) {
                i++;
            } else {
                // exact match
                break;
            }
        }
        
        System.out.println("Closest pair: [" + arr1[bestI] + ", " + arr2[bestJ] + "]");
        System.out.println("Sum: " + (arr1[bestI] + arr2[bestJ]) + ", Target: " + target);
        System.out.println("Diff: " + minDiff);
    }
    
    public static void main(String[] args) {
        int[] arr1 = {11, 56, 78, 99}; // ต้อง sorted!
        int[] arr2 = {12, 33, 69, 87}; // ต้อง sorted!
        int target = 79;
        
        closestPair(arr1, arr2, target);
    }
}

ผลลัพธ์

Closest pair: [11, 69]
Sum: 80, Target: 79
Diff: 1

Bug ในโค้ดต้นฉบับ: เปรียบเทียบกับ result_l (index) แทนที่จะเป็น target และ logic การ move pointer ผิด

Complexity

• Time: O(n + m) - แต่ละ pointer เคลื่อนที่ได้สูงสุด n+m ครั้ง
• Space: O(1)
• ต้องการ: ทั้งสอง array sorted แล้ว

ขยาย: Unsorted Arrays

Sort ก่อน O(n log n + m log m) แล้วค่อย two pointers รวม O(n log n + m log m)