——第一节：寻找满足条件的两个数题目： 1.输入一个有序的数组和一个数字， 在数组中查找两个数，使得它 们的和正好是输入的那个数字 例如：输入数组1、2、4、7、11、15和数字15由于4+11=15，因此 输出4和11 要求时间复杂度是O(n)如果有多对数字的和等于输入的数字， 输出任意一对即可思路分析：1.直接穷举，从数组中任意选取两个数，判定它们的和是否为输入的那个 数字此举复杂度为O（N^2）很显然，我们要寻找效率更高的解法2.题目相当于：对每个a[i]，然后查找判断sum-a[i]是否也在原始序列中 ，每一次要查找的时间都要花费为O（N），这样下来，最终找到两个数 还是需要O（N^2）的复杂度那如何提高查找判断的速度列? 二分查找，将原来O（N）的查找时间提高到O（logN），这样对于N个 a[i]，都要花logN的时间去查找相对应的sum-a[i]是否在原始序列中，总 的时间复杂度已降为O（N*logN），且空间复杂度为O（1）3.更好办法：用两个指针i，j，各自指向数组的首尾两端，令i=0，j=n-1 ，然后i++，j--，逐次判断a[i]+a[j]?=sum，如果某一刻a[i]+a[j]>sum，则 要想办法让sum的值减小，所以此刻i不动，j--，如果某一刻 a[i]+a[j]x) { --end; } else if(*begin+*end=M && t+W(k+1)=b[x[lev]]，那么将b[x[lev]]考虑进来。
假如已完成任务，那么结束否则进行后面的选择如果做到一定时 候发现无法深入下去，那么将刚选择的决定推翻（即回退），或考虑 其他选择或继续回退 ③.比如：m=10,n=3,k=3,以及k个数集合S={4,2,1}时，10=4+4+2，故10是满 足条件的数核 心 代 码课 外 思 考 题1.求一个整数用二进制表示时1的个数2.求500万以内的所有亲和数如果两个数a和b，a的所有因 数之和等于b,b的所有真因数之和等于a,则称a,b是一对亲和 数 例如： 220的因子是：1、2、4、5、10、11、20、22、44、55、110； 284的因子是：1、2、4、71、142220=1+2+4+71+142=sum[284],284=1+2+4+5+10+11+20+22+44+55+110=sum[220]sum[i]表示数i 的各个真因子的和 所以220和284是亲和数。