編程之美2.12——快速尋找滿足條件的兩個數或三個數

問題：
1. 快速找出一個數組中的兩個數，讓這兩個數之和等於一個給定的值。
2. 快速找出一個數組中的三個數，讓這三個數之和等於一個給定的值。

1. 解法：算法復雜度為O(nlogn)。先用快速排序對數組排序，讓後用雙指針（雙索引）法對排序好的數組進行反向遍歷，並且遍歷的方向不變。（若是計算兩個數的和，則初始化為i=0,j=n-1，若是計算兩個數的差，則初始化為i=0,j=1）
之所以這樣遍歷方式能成功，是因為排序後，若ai+aj<sum，則ai+ak<sum(k=i,i+1...j)，而i之前j之後的情況已遍歷過，所以只有i++才可能有等號的情況；若ai+aj>sum，則ak+aj>sum(k=i,i+1...j)，而i之前j之後的情況已遍歷過，所以只有j--才可能有等號的情況。
[cpp]
#include <iostream> 
#include <algorithm> 
using namespace std; 
 
#define MAXN 1001 
int A[MAXN]; 
 
// 總的時間復雜度為O(nlogn) 
int main() 
{ 
    int n, sum, i, j; 
    cin >> n >> sum; 
    for (i=0; i<n; i++) 
        cin >> A[i]; 
    // 快速排序O(nlogn) 
    sort(A, A+n); 
    // 雙索引反向遍歷 
    i=0; j=n-1;  www.2cto.com
    // 每個數只能用一次（若每個數可以用多次，則用<=） 
    while (i<j) 
    { 
        int plus = A[i]+A[j]; 
        if (plus == sum) 
        { 
            printf("(%d,%d) ",A[i],A[j]); 
            i++, j--; 
        } 
        else if (plus < sum) 
            i++; 
        else 
            j--; 
    } 
} 

2. 解法：時間復雜度為O(n^2)。如果數組已排序，利用解法1的雙指針遍歷法，可以在O(n)的時間內找到兩個數之和等於一個給定的數。我們假設找到的三個數ai,aj,ak有ai<=aj<=ak，要讓ai+aj+ak=sum，也就是要ai+aj=sum-ak，設subsum=sum-ak，很容易發現subsum的值只有n個，而確定ai+aj=subsum中的ai,aj只需要O(n)的時間，所以總的時間復雜度為O(nlogn+n*n)=O(n^2)
[cpp] 
#include <iostream> 
#include <algorithm> 
using namespace std; 
 
#define MAXN 1001 
int A[MAXN]; 
 
int main() 
{ 
    int n, sum, i, j, k; 
    cin >> n >> sum; 
    for (i=0; i<n; i++) 
        cin >> A[i]; 
    sort(A, A+n); 
    for (k=0; k<n; k++) 
    { 
        i=0; j=k-1; 
        if (k==i) i++; 
        if (k==j) j--; 
        int subsum = sum-A[k]; 
        while (i<j) 
        { 
            int plus = A[i]+A[j]; 
            if (plus == subsum) 
            { 
                printf("(%d,%d,%d) ",A[i],A[j],A[k]); 
                i++, j--; 
            } 
            else if (plus < subsum) 
                i++; 
            else 
                j--; 
            if (k==i) i++; 
            if (k==j) j--; 
        } 
    } 
} 

若允許每個數被多次選取，只需稍微改下代碼，具體如下：
[cpp] 
#include <iostream> 
#include <algorithm> 
using namespace std; 
 
#define MAXN 1001 
int A[MAXN]; 
 
int main() 
{ 
    int n, sum, i, j, k; 
    cin >> n >> sum; 
    for (i=0; i<n; i++) 
        cin >> A[i]; 
    sort(A, A+n); 
    for (k=0; k<n; k++) 
    { 
        i=0; j=k; 
        //if (k==i) i++; 
        //if (k==j) j--; 
        int subsum = sum-A[k]; 
        while (i<=j) 
        { 
            int plus = A[i]+A[j]; 
            if (plus == subsum) 
            { 
                printf("(%d,%d,%d) ",A[i],A[j],A[k]); 
                i++, j--; 
            } 
            else if (plus < subsum) 
                i++; 
            else 
                j--; 
            //if (k==i) i++; 
            //if (k==j) j--; 
        } 
    } 
} 

作者：linyunzju