yulu

算法-寻找和为定值的两个数

发表于

题目描述：
输入一个数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。要求时间复杂度是O(N)。如果有多对数字的和等于输入的数字，输出任意一对即可。例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。

分析：
分析在《编程之法：面试和算法心得》中寻找和为定值的两个数这一节，对于其中解法一中提到的用两个指针对两个数组分别进行扫描，若a[i] = a[j]时，即找到题目要求的数有点疑惑，在原作中没看到代码示例，所以写了一个php的简单实现。发现扫描的时候还是有点逻辑的。废话不多说，看代码吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
<?php
/**
*
*   FileName      ：t5.php
*   Version       ：1.0
*/
function find($arr,$sum){
	$tmp = array();
	foreach($arr as $item){
		$tmp[] = $sum - $item;
	}
	$list = [];
	for($i=0,$j=count($tmp)-1; $i<count($arr) && $j>0; ){
		if($arr[$i] > $tmp[$j]){
			$j--;
		}else if($arr[$i] < $tmp[$j]){
			$i++;
		}else if($arr[$i] == $tmp[$j]){
			$list[] = $arr[$i];
			$i++;
			$j--;
		}
	}
	return $list;
}
$arr = [1,2,4,7,11,15];
$ret = find($arr,15);

以上为解法一的实现。

解法二的hashtable实现用php就更简单了，php的数组本身就是一个hashtable，在此就不贴代码了。