算法精講：有序數組中兩數之和為S (雙指針O(n)解法 C語言實現)

雙指針法：在有序數組中查找和為S的兩個數

問題描述

給定一個遞增排序的整型數組和一個目標值S，找出數組中和為S的任意兩個數。若有多對，輸出任意一對即可。

核心思路：首尾雙指針向中間收斂

• 利用數組有序特性：left指向頭部(最小值)，right指向尾部(最大值)。
• 計算curSum = data[left] + data[right]：
• curSum == S：找到目標對，返回。
• curSum < S：和太小，需增大較小值 → left++。
• curSum > S：和太大，需減小較大值 → right--。
• 直到left >= right停止。

時間複雜度O(n)，空間複雜度O(1)，無需額外空間。

C語言完整實現

#include <stdio.h>
#include <stdbool.h>

bool FindNumbersWithSum(int data[], int length, int sum, int *num1, int *num2) {
    if (length < 2 || !num1 || !num2) return false;
    int left = 0, right = length - 1;
    while (left < right) {
        long curSum = (long)data[left] + data[right]; // 防溢出用long
        if (curSum == sum) {
            *num1 = data[left];
            *num2 = data[right];
            return true;
        } else if (curSum < sum) {
            ++left;
        } else {
            --right;
        }
    }
    return false;
}

int main(void) {
    int data[] = {1, 2, 4, 7, 11, 15};
    int num1, num2;
    if (FindNumbersWithSum(data, 6, 15, &num1, &num2))
        printf("num1 = %d, num2 = %d\n", num1, num2);
    else
        printf("Not found\n");
    return 0;
}

運行輸出

num1 = 4, num2 = 11

💡 關鍵細節

1. 輸入必須有序：無序數組需先排序(O(n log n))，整體複雜度仍優於暴力O(n²)。
2. 防整型溢出：兩大數相加可能超出int範圍，建議用long或long long暫存。
3. 去重需求：若需輸出所有不重複對，找到後left++、right--繼續搜尋並跳過重複值。