剑指offer之和为s的数组

1 问题

输入一个递增排序数组和数字和s,在数组里面找2个数，他们的和是s,如果有多对，只需要输出一对。
比如数组{1, 2, 4, 7, 11, 15}，我们输出4 ，11

2 思路

我们定义2个首尾指针，先是1+15，大于15，然后我们尾巴指针左移一下，然后就是1+11 小于15，然后首指针右移动一下，2+11，依次类推。
 

3 代码实现

  

   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     

      #include <stdlib.h>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      #define true 1
     
    
   

    

     

    
    

     

      #define false 0
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int findNumber(int *a, int len, int sum, int *num1, int *num2)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int result = false;	
     
    
   

    

     

    
    

     
	if (NULL == a || len < 1 || NULL == num1 || NULL == num2)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		return result;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	int start = 0;
     
    
   

    

     

    
    

     
	int end = len - 1;
     
    
   

    

     

    
    

     
	while (end > start)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		*num1 = a[start];
     
    
   

    

     

    
    

     

      		*num2 = a[end];
     
    
   

    

     

    
    

     
		int curSum = *num1 + *num2;
     
    
   

    

     

    
    

     
		if (curSum == sum)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			result = true;
     
    
   

    

     

    
    

     
			break;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		else if (curSum > sum)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			--end;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		else
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			++start;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return result;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int a[] = {1, 2, 4, 7, 11, 15};
     
    
   

    

     

    
    

     
 int num1 = 1;
     
    
   

    

     

    
    

     
 int num2 = 3;
     
    
   

    

     

    
    

     
 int result = findNumber(a, sizeof(a) / sizeof(int), 15, &num1, &num2);
     
    
   

    

     

    
    

     
 if (result == 1)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 printf("the num1 is %d the num2 is %d\n", num1, num2);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 printf("do not find the two number in numbers");
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

4 运行结果

the num1 is 4 the num2 is 11
 

5 代码优化

  

   

    

     

    
    

     
	while (end > start)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		int curSum = a[start] + a[end];
     
    
   

    

     

    
    

     
		if (curSum == sum)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			*num1 = a[start];
     
    
   

    

     

    
    

     

      			*num2 = a[end];
     
    
   

    

     

    
    

     

      			result = true;
     
    
   

    

     

    
    

     
			break;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		else if (curSum > sum)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			--end;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		else
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			++start;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
  
 

文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。

原文链接：chenyu.blog.csdn.net/article/details/98770167