荣誉版主
- 积分
- -2403
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2010-5-4
- 最后登录
- 1970-1-1
|
sort the array O(nlgn)
enumerate the first number, when the first number is fixed, use to two pointer to point to the start and the end of the array.
If the sum of the remaining two is greater than 0-first one then move the end pointer, other wise move the start pointer. O(n^2)
Total O(n^2)
danielgao 发表于 2011-9-4 13:34 ![]()
正确
- void Print3Sunm(int a[], int n)
- {
- assert(a && n > 0);
- sort(a, a + n);
- for (int i = 0; i < n-2; i++)
- {
- int nSum = -a[i];
- int p = i+1;
- int q = n-1;
- while (p < q)
- {
- if (a[p] + a[q] == nSum)
- {
- cout<<a[i]<<" "<<a[p]<<" "<<a[q]<<endl;
- return;
- }
- else if (a[p] + a[q] < nSum)
- p++;
- else
- q--;
- }
- }
- cout<<"Cannot find the number"<<endl;
- }
复制代码 |
|