[算法C++]檢測數組裡是否有兩個數之和等於某個數

[算法C++]檢測數組裡是否有兩個數之和等於某個數

問題：
檢測數組裡是否有兩個數之和等於某個數

解決方法一：先將數組排序，然後從兩頭開始遍歷
數組排序後，從左端開始取最小值，從右端取最大值，
判斷兩者之和與目標的大小：
1. 等於時，輸出兩個數；
2. 大於時，右端移到第2個數，繼續判斷；
3. 小於時，左端移到第2個數，繼續判斷。

#include 
#include 
#include 
using namespace std;

void fun1(int a[], int length, int target) {
    // 給數組排序
    sort(a, a + length);
    // left是最小值，right是最大值
    int left = 0, right = length - 1;
    while (left < right) {
        int tmp = a[left] + a[right];
        if (tmp == target) {
            cout << a[left] << a[right] << endl;
            return;
        }
        else if (tmp > target) { // 和比目標大，就減小right，從而減小和
            right--;
        }
        else {  // 和比目標小，就增大left，從而增大和
            left++;
        }
    }
    cout << 無 << endl;
}

int main() {
    int a[] = {
        1, 3, 2, 7, 6, 9, 8, 0, 5, 4
    };

    int target = 0;
    while (cin >> target) {
        fun1(a, 10, target);
    }
}

上述方法雖然簡單，但弊端也有，沒法輸出所有等於目標值的兩個數。

解決方法二：
暴力解法，記錄下每一個數與其他數的和放在一個二維數組裡，然後遍歷即可，這樣可以記錄下所有的和等於目標值的數值對，如下：
假設輸入數組為: 2 3 4 5 1
有如下矩陣：

  2 3 4 5 1 2 - 5 6 7 3 3 5 - 7 8 4 4 6 7 - 9 5 5 7 8 9 - 6 1 3 4 5 6 -

當目標值為7時，就有兩組：
（5,2）與（3,4）
考慮到對稱性，有n[i][j] = n[j][i],i!=j,
，所以，我們只需要i>j的數值對就行。

void fun2(int a[], int length, int target) {
    int** n = new int*[length];
    for (int i = 0; i < length; i++) {
        n[i] = new int[length];
    }
    for (int i = 0; i < length; i++) {
        for (int j = length - 1; j > i; j--) {
            n[i][j] = n[j][i] = a[i] + a[j];
        }
    }
    for (int i = 0; i < length; i++) {
        for (int j = length - 1; j > i; j--) {
            if (n[i][j] == target) {
                cout << a[i] <<   << a[j] << endl;
            }
        }
    }

}