面试100 26求和为给定值的连续序列

    26 和为给定值的连续序列

 一 问题描述
      和为n的正数序列，比如求合为15的正数连续序列，则有以下序列满足
    12345 == 456 == 78
    解题思路：
     设置一个small =1 ,big=2
     求 sum = [small , big]
   
    若sum 大于15 ，则small左移，相当于去掉最小值。
    若sum 小于15 ，则big  右移， 相当于增加最大值。  

   扩展如下：
     若在一个已经排序的序列中，求两个元素之和为定值的元素。
    可以使用left ,right分别表示，序列中的首尾元素，若left+right 大于给定和，则right--，若小于则left++。 与此题的思路相似。

#include <iostream>
  using namespace std ;
  int H = 15 ;
  
  int sum(int l , int h)
  {
     int i , sum = 0;
     for(i = l ; i <= h ;i++) 
       sum += i ;
       
       return sum ;
  }
  
  void findsequence(int n)
  {
       int small = 1 ;
       int big = 2 ;
       
       while(small < (n + 1) / 2)
       {
          int sums = sum(small , big);          
         if( sums < H)
           big++ ;
         else
         if(sums == H)         
         {
           cout<<small<<"--->"<<big<<endl ;                             
           small++ ;
         }
        else
          small++ ;  
                     
       }
       
  }
  
  int main()
  {
   findsequence(H) ;
   system("pause") ;
   return 0 ;    
  }

posted on 2011-05-19 13:46 kahn 阅读(233) 评论(0)  编辑 收藏 引用