常见算法之6---判断集合S之中是否存在两个数之和为指定大小N

(注:本题是2题的完善)

题目:判断集合S之中是否存在两个数之和为指定大小N

示例: 集合S={1,5,3,7,9,3,2,8} N=10

输出:yes

方案1:集合是无序的,那么我们必须将各种两两组合的数相加,来判断,这样的时间复杂度为O(n*n)。

方案2:倘若集合是有序的,我们能不能利用有序这个条件呢?
  1 我们可以使用一种平均性能不错的排序,先将集合进行排序,O(nlogn)。
  2 从前向后逐一遍历集合,若当前元素s[i] = i,有因为集合也是有序的,可以用二分查找来找N-i是否存在。
    2.1 若存在,则输出yes
    2.2 否则,继续向后重复此过程,直到结束。
  综上,时间复杂度O(nlogn+nlogn)~O(nlogn)

方案3:
  1 我们可以使用一种平均性能不错的排序,先将集合进行排序,O(nlogn)。
  2 然后设定两个指针(前指针指向第一个元素,后指针指向最后一个元素。)
  3 倘若前指针指向的数加上后指针的和等于N,那么输出yes
  4 否则
    4.1 若是(前指针+后指针)<N,那么将后指针向前移动一位,再判断;
    4.2 若是(前指针+后指针)>N,那么将前指针向后移动一位,再判断。
  5 若是前后两个指针相遇了,还没有遇到等于N,输出no。
  这样的话,相当于遍历一遍集合,O(n)。所以最后总的时间复杂度为O(nlogn+n)~O(nlogn)。
  本质:不断地以最小的跳跃幅度去逼近N。

原文地址:https://www.cnblogs.com/xiaoChongUp/p/3323094.html