a**********0
发帖数: 422 | 1 简单的解法 知道set的range 产生一个int array ： int[range] 保证内容和
index一样 （当然为了space可以红hash的版本 此处不是讨论这个问题） sweep整个
set 看 sum-i是不是在array之中
但是如何克服一个corner situation？ 比如sum = 8 set之中只有一个4 这样自
己相当于用了两次
是不是加一个简单的判别 如果sum=2i （当然这种情况必须运用hash了） 看相应的bin
下是否有多于一个的i |
c*****t
发帖数: 48 | 2 先排序 O(n)
然后从两头往中间扫，直到找到两个数和=sum或者两个index碰头了，这一步也是O(n)
bin
【在 a**********0 的大作中提到】
: 简单的解法 知道set的range 产生一个int array ： int[range] 保证内容和
: index一样 （当然为了space可以红hash的版本 此处不是讨论这个问题） sweep整个
: set 看 sum-i是不是在array之中
: 但是如何克服一个corner situation？ 比如sum = 8 set之中只有一个4 这样自
: 己相当于用了两次
: 是不是加一个简单的判别 如果sum=2i （当然这种情况必须运用hash了） 看相应的bin
: 下是否有多于一个的i
|
a**********0
发帖数: 422 | 3 如果扩展到找三个数whose sum 已知 时间复杂度可以做到多少？ |
a**********0
发帖数: 422 | 4 我觉得你的意思是用线性的sort
第二步骤是判断sum和两个指针的sum比谁的大 如果sum大则左边指针向右移动 否则右
边指针向左移动 碰头就是没有
【在 c*****t 的大作中提到】
: 先排序 O(n)
: 然后从两头往中间扫，直到找到两个数和=sum或者两个index碰头了，这一步也是O(n)
:
: bin
|
c*****t
发帖数: 48 | 5 对
你的那个corner case也自动解决了
【在 a**********0 的大作中提到】
: 我觉得你的意思是用线性的sort
: 第二步骤是判断sum和两个指针的sum比谁的大 如果sum大则左边指针向右移动 否则右
: 边指针向左移动 碰头就是没有
|
j*******t
发帖数: 223 | 6 这不就是2sum么，第一遍扫了放入hashmap，第二遍找hashmap中是否有target - val。
唯一要判断就是是否有值为target / 2。这个在放入hashmap的时候判断下就可以了。 |
r******l
发帖数: 10760 | 7 O(n)咋排序？
【在 c*****t 的大作中提到】
: 先排序 O(n)
: 然后从两头往中间扫，直到找到两个数和=sum或者两个index碰头了，这一步也是O(n)
:
: bin
|
i*******e
发帖数: 69 | 8 What is the set is really large? |
t**********r
发帖数: 2153 | 9 加count
bin
【在 a**********0 的大作中提到】
: 简单的解法 知道set的range 产生一个int array ： int[range] 保证内容和
: index一样 （当然为了space可以红hash的版本 此处不是讨论这个问题） sweep整个
: set 看 sum-i是不是在array之中
: 但是如何克服一个corner situation？ 比如sum = 8 set之中只有一个4 这样自
: 己相当于用了两次
: 是不是加一个简单的判别 如果sum=2i （当然这种情况必须运用hash了） 看相应的bin
: 下是否有多于一个的i
|
c***0
发帖数: 449 | 10 我一直不明白为什么要先全扫一遍再找，为什么不能先判断sum-a[i]存在不存在，如果
存在就找到了，如果不存在就是找不到，不就解决了？
for each i in a
{
if sum-a[i] exist in hash
found
else
not found
hash insert a[i]
}
这样不是边扫边找嘛。 |
|
|
y*****3
发帖数: 451 | 11 什么排序可以做到O(n)？请指教
【在 c*****t 的大作中提到】
: 先排序 O(n)
: 然后从两头往中间扫，直到找到两个数和=sum或者两个index碰头了，这一步也是O(n)
:
: bin
|
o*********r
发帖数: 203 | 12 It's possible for some set of numbers, if:
1. size is relatively small
2. smallest and largest values are known
for example:
arr = [4, 6, 3, 0, 10]
you know that:
- smallest = 0,
- largest = 10
so you can create a int array of size 11:
temp = int[11] {};
for i in arr {
temp[i] = 1;
}
index of temp (having value of 1) contains the sorted 'arr'.
【在 y*****3 的大作中提到】
: 什么排序可以做到O(n)？请指教
|
m*f
发帖数: 8162 | 13 re
【在 c***0 的大作中提到】
: 我一直不明白为什么要先全扫一遍再找，为什么不能先判断sum-a[i]存在不存在，如果
: 存在就找到了，如果不存在就是找不到，不就解决了？
: for each i in a
: {
: if sum-a[i] exist in hash
: found
: else
: not found
: hash insert a[i]
: }
|
r******l
发帖数: 10760 | 14 有重复的怎么办？float怎么办？
【在 o*********r 的大作中提到】
: It's possible for some set of numbers, if:
: 1. size is relatively small
: 2. smallest and largest values are known
: for example:
: arr = [4, 6, 3, 0, 10]
: you know that:
: - smallest = 0,
: - largest = 10
: so you can create a int array of size 11:
: temp = int[11] {};
|
m*f
发帖数: 8162 | 15 why you guys choose to ignore what cc150 has suggested |
