找出已排序数组中差为给定值的两个数

常见的题目是找出和为给定值的两个数，现在换成差为给定值。有没有什么好方法？

难道不能跟和为定值一样的办法找么。
第一次遍历存hashset
第二次遍历看加减x是否在hashset里

wobushimm 发表于 2013-12-22 12:53
难道不能跟和为定值一样的办法找么。
第一次遍历存hashset
第二次遍历看加减x是否在hashset里

如果不想用hash呢……

排序， 用两个指针head 和 tail，观测n[tail] - n[head] 如果差大于target， 移动head向前， 如果小于， 移动tail. 注意， 考虑target是负数的情况， tail有可能<head。

OracleDesire 发表于 2013-12-22 00:02
如果不想用hash呢……

不用就排序然后对分查找，nlogn，不知道怎么不用hash做到n

北美农民 发表于 2013-12-22 01:17
排序， 用两个指针head 和 tail，观测n[tail] - n[head] 如果差大于target， 移动head向前， 如果小于， 移 ...

这个只能找到一个解吧。可能存在多个解。

而且你这个，head tail的初始值是哪里？

北美农民 发表于 2013-12-22 13:17
排序， 用两个指针head 和 tail，观测n[tail] - n[head] 如果差大于target， 移动head向前， 如果小于， 移 ...

比较同意这个算法，但是为什么大家动用linked list呢？不是说数组吗？ 这个算法应该是可以找到所有的结果的，因为是排序的只要遍历一趟就可以了。

我有一个相仿不知道对不对，还没有验证：
1，初始化两个位置变量a,b，开始都指向数组头（因为数组是排序的）
2，b向后遍历数组，每经过一个数，a指向的数就加一个或者建一个给定数x。
3， 如果b-x>a,a前进，否则b前进。直到b到数组尾部。