Check if the sum of two integers in an integer array eqauls to the given number - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

Check if the sum of two integers in an integer array eqauls to the given number

Check if the sum of two integers in an integer array eqauls to the given number# Programming - 葵花宝典

z*e2007-06-07 07:06

1 楼

I saw a similar post in this board, and recalled my recent interview
experience. Got this question in Amazon interview. Although I failed, it is
still a good one.
My answer:
1. Create a hash table to store all integers in this array. O(n)
2. For each int, look for sum - int in the created hash tree. Since hash
tree is the fastest look-up table, we can take advantage from it. n*O(1)
3. So this is O(n) algorithm.
Then the guy gave me the array 1, 2, 10, 20, sum is 2. My answer will return
true obv

o*r2007-06-07 07:06

2 楼

What if you have a collision in setting up hash table.
Do you use list?
A simple solution is just count occurrence of a value.
Since it only needs to be checked when value == S/2,
the occurrence count doesn't affect much.

is
return

【在 z***e 的大作中提到】

: I saw a similar post in this board, and recalled my recent interview
: experience. Got this question in Amazon interview. Although I failed, it is
: still a good one.
: My answer:
: 1. Create a hash table to store all integers in this array. O(n)
: 2. For each int, look for sum - int in the created hash tree. Since hash
: tree is the fastest look-up table, we can take advantage from it. n*O(1)
: 3. So this is O(n) algorithm.
: Then the guy gave me the array 1, 2, 10, 20, sum is 2. My answer will return
: true obv