Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1006687
  • 博文数量: 150
  • 博客积分: 3017
  • 博客等级: 少校
  • 技术积分: 3829
  • 用 户 组: 普通用户
  • 注册时间: 2011-11-19 14:40
个人简介

Now in Baidu WISE team

文章分类

全部博文(150)

文章存档

2014年(8)

2013年(31)

2012年(111)

分类: C/C++

2012-10-03 14:05:20

题目:输入一个已经按升序排序过的数组和一个数字,
在数组中查找两个数,使得它们的和正好是输入的那个数字。
要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字,输出任意一对即可。
例如输入数组1、2、4、7、11、15和数字15。由于4+11=15,因此输出4和11。

简单题,两个指针一个指头,一个指尾。
如果和超过15,那么尾部往回走一步。
如果和不到15,那么头指针往前走一步

点击(此处)折叠或打开

  1. /*
  2.  * =====================================================================================
  3.  *
  4.  * Filename: findsum.c
  5.  *
  6.  * Description:
  7.  *
  8.  * Version: 1.0
  9.  * Created: 10/03/2012 01:44:40 PM
  10.  * Revision: none
  11.  * Compiler: gcc
  12.  *
  13.  * Author: YOUR NAME (),
  14.  * Organization:
  15.  *
  16.  * =====================================================================================
  17.  */
  18. #include <stdlib.h>
  19. #include <stdio.h>


  20. void findsum(int *num, int size, int tar){
  21.     int *head = num;
  22.     int *tail = head+size -1;
  23.     while(head<tail){
  24.         if(*head + *tail == tar){
  25.             printf ( "%d + %d = %d\n",*head, *tail, tar );
  26.         }
  27.         if(*head + *tail < tar) {
  28.             head++;
  29.         }
  30.         else{
  31.             tail --;
  32.         }
  33.     }
  34. }

  35. /*
  36.  * === FUNCTION ======================================================================
  37.  * Name: main
  38.  * Description:
  39.  * =====================================================================================
  40.  */
  41.     int
  42. main ( int argc, char *argv[] )
  43. {
  44.     int nums[] = {1,2,4,7,11};
  45.     findsum(nums, sizeof(nums)/sizeof(int), 15);

  46.     return EXIT_SUCCESS;
  47. }                /* ---------- end of function main ---------- */

阅读(883) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~