糯米

TI DaVinci, gstreamer, ffmpeg
随笔 - 167, 文章 - 0, 评论 - 47, 引用 - 0
数据加载中……

小程序:给出n个数,如何找出三个数,它们的和等于k

通常的思路是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[] = {12545102351};

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;
}


posted on 2010-11-21 23:10 糯米 阅读(386) 评论(0)  编辑 收藏 引用 所属分类: Algorithm


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理