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

问题描述

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

应用8：假设有一个整数类型的顺序表，元素取值可能是1~N（10<=N<=100000）中的任意一个数，相同数值不会重复出现。试设计一个算法，用O(n)的时间复杂度将找出顺序表中符合条件的数对的个数，满足数对中两数的和等于N+1。

参考函数原型：

template
   
         int getCount(const vector
    
      &A, int N);
    
   

函数形参：

A: 整数类型的顺序表，其元素取值可能是1~N（10<=N<=100000）中的任意一个数N: 在A中，查找两个数的和等于N+1的对数

函数返回值：

返回统计结果

输入说明

第一行：两个数Len和N，分别表示A的长度以及给定的N值，以空格分隔

第二行：顺序表的数据元素（取值可为1~N中的任意一个数），以空格分隔

输出说明

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

空行

第二行：统计结果

输入范例

10 1001 100 2 99 3 97 10 91 4 5

输出范例

1 100 2 99 3 97 10 91 4 5 4

思路分析

• 分析题目，有两个需要注意的地方
  • 元素的范围是限定的，并且是已知的，是在1~N之间的。并且的每个元素是不相同的
  • 使用的O（n）的时间复杂度去查找所有符合条件的对数的个数，意味着，不可以使用暴力法求解
• 经验：根据以前的经验，对于这类的题目限定时间复杂度为O（n）的情况下，也就两种方法：
  • 数组已经排过序，使用的two point法，从两边向中间遍历，详见
  • 数组没有排序，使用的万能的hashmap，通过hash表能快速定位到的对应的位置，不需要查找。
• 思考：
  • 首先，向量是乱序的，是随机的，所以不可以使用的two point法，我知道的，大部分的排序方法都是的O（n²）或者以上的，所以排除这种方法
  • hashmap必须使用hashmap来实现。虽然这里限定了使用的数据类型，必须使用vector，但是这里也限定了数字的范围的，并且不能重复
  • 于是乎，不难想象，用vector来模仿hashmap。
• 用vector来模仿hashmap
  • hashmap是key-value键值对，vector是index - value
  • 使用index来表示数字，用value来表示该数字是否存在，存在为1，不存在为0
  • 通过查询msdn知道，无论索引是多大，vector检索到对应的位置时间都是固定的，所以不用担心会时间复杂度。

问题解决

• 好吧，这就不好猜了。凭经验来讲，一般来说是三种情况：下限，等值和上限。但是这里有五种情况，只能一个一个试试三种情况了。
• 情况一，等值对为零
  
• 情况二，有几个正常的等值

• 情况三、全是等值

• 好吧，三种情况都可以，是否可能是非法输入？肯定不会是有相同的数据，这是题目的前提！好吧！想测试样例是那么的难受，我还是花一分去买一个样例吧

• 显而易见的，a + b = 100，a和b不一定相同，也可能一样，50+50=100，第一次遍历到五十，刚好五十的位置并没有置空，所以就会多出来一个。

• 修改：改一下逻辑顺序，遍历的每一个数字a，先将自己的hashmap置为零，表示不存在，再取出看对位（100 - a）是否存在
  
• 😔，这个样例居然又0.3，心疼啊！

分析与总结

• 想出来了就好了，但是居然在一个地方纠结了半天
  
• 参数被自己搞反了，assign（复制的数目，复制的对象）。弄反了，写成（0，sum+1）。有点太想当然了，还费了一番功夫，最后恍然大悟，自己居然没有的看清。

源码

• 兄弟，关注了，就留个言吧！源码是不会给的，你要是有局部不会，我还是可以发局部的。毕竟老师会查重的，万一大家都一样，重写就不好了！

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