【正确答案】正确答案：基本设计思想：如果我们不考虑时间复杂度，最简单的想法是先在数组中固定一个数字，再依次判断数组中剩下的n—1个数字与它的和是不是等于输入的数字。可惜这种思路需要的时间复杂度是O(n ² )，不满足题意要求。 假设现在随便在数组中找到两个数，如果它们的和等于输入的数字，那太好了，我们找到了要找的两个数字；如果小于输入的数字呢？我们希望两个数字的和再大一点。由于数组已经排好序了，我们是不是可以把较小的数字往后面移动一个数字？因为排在后面的数字要大～些，那么两个数字的和也要大一些，就有可能等于输入的数字了；同样，当两个数字的和大于输入的数字的时候，我们把较大的数字往前移动，因为排在数组前面的数字要小一些，它们的和就有可能等于输入的数字了。 我们把前面的思路整理一下：最初我们找到数组的第一个数字和最后一个数字。当两个数字的和大于输入的数字时，把较大的数字往前移动；当两个数字的和小于数字时，把较小的数字往后移动；当相等时，正合题意。

【正确答案】正确答案：算法实现如下： } if (count==n) //n为该有向图中结点的总数 yes=1； return yes； } 方法二：深度优先遍历（使用栈） int rdfs (ADJLIST g，int vi) { int i，count， yes； yes=0； count=1； stack s； for(int i=0； i＜n； i++)visited[i] =0；//初始化访问标记数组 push (vi，s) ； visited [vi]=i； //初始化 while ( ! empty (s) &&yes—=0) { int w=top (s) ； p=g[w]，firstarc； while(p !=NULL&&visited[p—＞adj data]) { p=p—＞next； if (p==NULL) pop (s)； else { w=p—＞adjdata； visited [w]=1； count++； push (w， s) ； } } } if(count==n)//n为该有向图中的结点数 yes=1； return yes； }

【正确答案】正确答案：时间复杂度分析：在while的循环中，每次根据curSum和sum之间的大小关系来决定改变ahead还是改变behind。这个过程每次是O(1)的。在整个算法流程中，因为ahead始终大于behind的，如果一个数被ahead扫过了，那么它不会被behind扫到，也不会被ahead再次扫到；同样的，如果一个数被behind扫过了，那么它将不会再被ahead或者behind扫到。所以循环最多执行n—1次就会结束，故整个算法的时间复杂度为O(n)。