【EMC笔试题】N个整数中找出三个数，使其和的绝对值最小
转自：http://blog.csdn.net/BusyCai/article/details/6155929
?
题目描述：给定包含N个数的无序数组S（可能包含负数，0，正数）。求三个数A,B,C，使其和的绝对值最小。
例如：S={-9，0，1，3，6}，A=-9,B=3,C=6,MIN=0算法解析：解法一：枚举3个数，O(N*N*N)解法二：对S排序后枚举其中2个数，二分查找另一个数。O(N*N*LOGN)
解法三：对S排序后枚举其中1个数X，使用双向指针i,j从数组两端更新（注意剔除X）。根据S[I]+S[J]+X的正负号来更新I或J。若为负则I++，否则J--。一旦和为0即退出。同时根据每次得到的和来更新best。最后best即为所求。利用三个变量X,Y,Z记录，可得到任一最优解。复杂度O(N*lOGN+N*N)=O(N*N）
?
期待更好解法 ：）
例如S={-9,0,1,3,6,10}X=-90 1 3 6 10i?????????? jX+S[i]+S[j]=-9+0+10=1 > 0 j--0 1 3 6 10i??????? jX+S[i]+S[j]=-9+0+6=-3 < 0 i++0 1 3 6 10??? i????? jX+S[i]+S[j]=-9+1+6=-2 < 0 i++0 1 3 6 10???? i?? jX+S[i]+S[j]=-9+3+6=0 = 0 quitMIN=0,X=-9,Y=3,Z=6;-----------------------------------------算法二没看懂啊?
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <algorithm>
using std::sort;
int main()
{
????int a[100], b[100];
????int X,Y,Z;
????int i, j, k;
????int best;
????srand((unsigned)time(NULL));
????int KASE = rand()%10;
????for(int kase = 1; kase <= KASE; kase++){
????printf("/nCase #%d :/n", kase);
????int n = rand()%20;
????if(n <= 2) { printf("Sorry, n is less than 3. /n"); continue; }
????for(i = 0; i < n; i++){
???????? a[i] = rand()%100;
????????if(rand()%2) a[i] *= -1;
????}
????sort(a,a+n);
????for(i = 0; i < n; i++) printf("%d ", a[i]); printf("/n");
????int STD = 1000000;
????for(i = 0; i < n; i++)
????????for(j = i+1; j < n; j++)
????????????for(k = j+1; k < n; k++)
????????????????if(abs(a[i]+a[j]+a[k]) < STD){
???????????????????? X = a[i]; Y = a[j]; Z = a[k];
????????????????????STD = abs(a[i]+a[j]+a[k]);
????????????????}
????printf("STD answer is: MIN=%d, X=%d Y=%d Z=%d/n", STD, X, Y, Z);
???? best = 1000000;
????for(i = 0; i < n; i++){
????????int cur = a[i];
????????int cnt = 0;
????????for(j = 0; j < n; j++){
????????????if(j != i) b[cnt++] = a[j];
????????}
????????int head = 0, tail = n-2;
????????while(head < tail){
????????????int now = cur + b[head] + b[tail];
????????????if(now == 0 || abs(now) < best){
???????????????? best = abs(now);
???????????????? X = cur;
???????????????? Y = b[head];
???????????????? Z = b[tail];
????????????????if(now == 0) break;
????????????}
????????????if(now < 0) head++;
????????????else tail--;
????????}
????????if(best == 0) break;
????}
????printf("My answer is: MIN=%d, X=%d Y=%d Z=%d/n", best, X, Y, Z);
????}
????system("pause");
}
