編程之美 2.12：有序數組雙指針 O(n) 尋找和為定值的兩個數

編程之美 2.12：雙指針法在有序數組中尋找目標和

題目：在數組中找兩個數，和等於給定值 S。暴力 O(n²)，排序後雙指針 O(n log n)（排序主導）或 O(n)（已有序）。

雙指針核心邏輯

數組升序。左指針 i=0，右指針 j=n-1。
- 若 A[i]+A[j] == S → 找到。
- 若 > S → 和太大，右指針左移 j--。
- 若 < S → 和太小，左指針右移 i++。
終止條件：i ≥ j。

完整代碼

void DutQuickFindSpecifyTwoNums(int* A, int size, int sum, int& one, int& two) {
    if (!A || size <= 1) { one=two=-1; return; }
    sort(A, A+size); // 若已有序可省略
    int i=0, j=size-1;
    while (i < j) {
        int s = A[i] + A[j];
        if (s == sum) { one=A[i]; two=A[j]; return; }
        else if (s > sum) --j;
        else ++i;
    }
    one=two=-1;
}

變體與擴展

• 找所有配對：找到後 i++、j-- 繼續，注意去重。
• 三數之和：固定一數，剩餘雙指針，O(n²)。
• 最近和：記錄最小差值對，遍歷完返回。

複雜度

排序 O(n log n)，雙指針掃描 O(n)，空間 O(1)。若數組本身有序則 O(n)。