通常的思路是O(N^3)
但可以有小小优化:
一。先排序
二。枚举i, j, k的时候,固定i的时候,j和k分别从左从右扫描数组,直到两个碰到为止。
三。对于每个i,k从右扫描的开始位置是递减的。
然后就有了下面的小程序:
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
int N = 10;
int K = 5;
int arr[] = {1, 2, 5, 4, 5, 10, 2, 3, 5, 1};
int main()
{
int a, b, c, i;
sort(arr, arr + N);
c = N - 1;
for (a = 0; a < c; a++) {
for (b = a + 1; b < c; b++) {
while (c >= 0 && arr[a] + arr[b] + arr[c] > K)
c--;
for (i = c; b < i; b++) {
while (i >= 0 && arr[a] + arr[b] + arr[i] > K)
i--;
if (i >= 0 && arr[a] + arr[b] + arr[i] == K)
printf("%d %d %d\n", arr[a], arr[b], arr[i]);
}
}
}
return 0;
}