問題:
檢測數組裡是否有兩個數之和等於某個數
解決方法一:先將數組排序,然後從兩頭開始遍歷
數組排序後,從左端開始取最小值,從右端取最大值,
判斷兩者之和與目標的大小:
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
有如下矩陣:
當目標值為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;
}
}
}
}