本文共 1488 字，大约阅读时间需要 4 分钟。

问题描述

目的：使用STL的vector模板设计并实现顺序表应用场合的一些简单算法设计。

应用7：试设计一个算法，找出有序顺序表A（顺序表A中的数据元素的数据类型为int型）中两个元素和为给定值sum的所有元素对，并保持原有序表不变。

参考函数原型：

template
   
    void Search_Pairs( vector
    
      &A, int sum )；
    
   

输入说明

第一行：有序顺序表A的长度

第二行：有序顺序表A的数据元素（数据元素之间以空格分隔）

第三行：给定值sum

输出说明

第一行：顺序表A的遍历结果

第二行开始：符合条件的元素对（每一对占一行，数据元素之间以","分割）

如无符合条件的元素对，输出"NULL"

输入范例

61 3 5 7 9 1510

输出范例

1 3 5 7 9 15 1,93,7

思路分析

• 比起双重遍历的暴力求解，可以参考一下如下的two points方法

错误提取

• 分析：
  • 如果是给的序列不一定是升序，是降序，那判定条件不就反了？
  • 如果有重复的元素，不会重复输出吗？
• 对策：
  • 首先针对重复元素，移动元素之前先判定一下，防止下一个元素是重复的。
    

• 通过了，好吧，确实只是重复的元素，OJ的样例太少了，比leetcode的难度低多了

实现源码

#include 
   
    #include 
    
     using namespace std;/*    description:show all the elements of the vector*/template
     
      void show(vector
      
       & A){
       typename std::vector
       
         test = A;    typename std::vector
        
         ::iterator iter; for(iter = test.begin();iter != test.end();iter ++) { cout<<*iter<<" "; } cout<
         
          void Search_Pairs( vector
          
            &A, int sum ){ typename std::vector
           
            ::iterator iterB = A.begin(); typename std::vector
            
             ::iterator iterE = A.end(); bool isFlag = false; while(iterB < iterE) { if((*iterB + *iterE) == sum) { isFlag = true; cout<<*iterB<<","<<*iterE<
             
               sum) { iterE --; } if((*iterB + *iterE) < sum) { iterB ++; } } if(!isFlag) { cout<<"NULL"<
              
               >Asize; vector
               
                 A(Asize); int str; for(int i = 0 ;i < Asize;i ++) { cin>>str; A.at(i) = str; } int target; cin>>target; show(A); Search_Pairs(A,target); return 0;}
               
              
             
            
           
          
         
        
       
      
     
    
   

分析与总结

• leetcode还是要刷起来的，oj的题目是要习惯了这种模式，还是很简单的

转载地址：http://xwwvb.baihongyu.com/