Cracking the coding interview--Q19.11
Design an algorithm to find all pairs of integers within an array which sum to a specified value.
译文：
设计一个算法，找到数组中所有和为指定值的整数对。
解答
时间复杂度O(n)的解法
我们可以用一个哈希表或数组或bitmap(后两者要求数组中的整数非负)来保存sum-x的值， 这样我们就只需要遍历数组两次即可找到和为指定值的整数对。这种方法需要O(n) 的辅助空间。如果直接用数组或是bitmap来做，辅助空间的大小与数组中的最大整数相关， 常常导致大量空间浪费。比如原数组中有5个数：1亿，2亿，3亿，4亿，5亿。sum为5亿， 那么我们将bitmap中的sum-x位置1，即第4亿位，第3亿位，第2亿位，第1亿位，第0位置1. 而其它位置都浪费了。
如果使用哈希表，虽然不会有大量空间浪费，但要考虑冲突问题。
Read full article from Cracking the coding interview--Q19.11
No comments:
Post a Comment