LinkedIn 面試題：數組中尋找和為 N 的兩數

題目

給定整數數組，找出是否存在兩個數之和等於給定值 sum。若存在輸出該對，否則提示無解。

解法：排序 + 雙指針

1. 對數組排序（O(N log N)）。
2. 左右指針 i=0, j=n-1：

• 若 A[i]+A[j] == sum → 找到，返回。
• 若 < sum → i++（需增大和）。
• 若 > sum → j--（需減小和）。

時間 O(N log N)，空間 O(1)（原地排序）。

完整 C++ 代碼

#include 
#include 
#include 
#include 

int randomPartition(int A[], int low, int high) {
    int idx = low + rand() % (high - low + 1);
    std::swap(A[idx], A[high]);
    int key = A[high];
    int i = low - 1;
    for (int j = low; j < high; ++j) {
        if (A[j] <= key) {
            ++i;
            std::swap(A[i], A[j]);
        }
    }
    std::swap(A[i+1], A[high]);
    return i + 1;
}

void quickSort(int A[], int low, int high) {
    if (low >= high) return;
    int p = randomPartition(A, low, high);
    quickSort(A, low, p - 1);
    quickSort(A, p + 1, high);
}

bool findPair(int A[], int n, int sum, std::pair& res) {
    quickSort(A, 0, n - 1);
    int i = 0, j = n - 1;
    while (i < j) {
        int s = A[i] + A[j];
        if (s == sum) {
            res = {A[i], A[j]};
            return true;
        } else if (s < sum) ++i;
        else --j;
    }
    return false;
}

int main() {
    int A[] = {-2, -5, 1, 4, 3, 9, 6, 5, 7, 0};
    int sum;
    std::cout << "Please enter a sum value\n";
    std::cin >> sum;
    std::pair ans;
    if (findPair(A, 10, sum, ans))
        std::cout << ans.first << "+" << ans.second << " = " << sum << "\n";
    else
        std::cout << "No pair found\n";
    return 0;
}

代碼亮點與改進建議

• 隨機化快排：randomPartition 避免最壞 O(N²)，但 srand(time(0)) 應放在 main 開頭，不要在 partition 內重複調用（會導致同秒內隨機數相同）。
• 標準庫替代：實際工程直接用 std::sort（IntroSort，保證 O(N log N)）與 std::pair，代碼更簡潔健壯。
• 邊界情況：數組含重複元素、負數均正確處理；若要求返回原始索引，需排序前保存 (value, index) 對。
• 哈希表解法：若允許 O(N) 空間，單遍歷用 unordered_set 記錄已見元素，查找 sum - x，時間 O(N) 平均，適合不可排序或需原索引場景。

複雜度對比

總結

「兩數之和」是經典面試必考題。掌握排序+雙指針（空間最優）與哈希表（時間最優）兩種核心解法，並能分析隨機化快排、標準庫替代、邊界處理等工程細節，即可從容應對 LinkedIn 等大廠面試。