r***u
发帖数: 241 | 1 就是一个数组中找两个数使得它们的和为一个给定的数。
今天被纠缠问了好久，先从两个数，推广到3个数，再到4个数，和k个数。
最后也不知道答对了没有，板上好像有讨论把？ | p********7
发帖数: 549 | 2 2个数,先查 sum - a[i] 是否在hashtable里面,如果在就返回true,如果不在就插入a[i
] O(N)
3个数,有点不同,因为3个数有可能是一样的,这样查起来会有问题,所以先排序,处理了
特殊的有2个数重复,或者三个数重复的情况,再查 sum - a[i] - a[j]是不是在,复杂读
是O(N^2)
k个数就更复杂了,复杂度接近brute force 复杂度O(N^(k-1)) | d*****t
发帖数: 41 | 3 类似楼上，但是用递归。
两个数，查sum-a[i]，在HASHTABLE里就返回TRUE，不在就添加。
三个数，从数组中取出a[j],和数组最后一位a[N-1]交换位置。sum' = sum - a[N]，然
后对数组的a[0]~a[N-2]位，换两个数求和处理。
比较直观，但是空间复杂性比较大 | a****n
发帖数: 1887 | 4 O(N^(K/2))空间, O(N^((K+1)/2))时间
[i
【在 p********7 的大作中提到】
: 2个数,先查 sum - a[i] 是否在hashtable里面,如果在就返回true,如果不在就插入a[i
: ] O(N)
: 3个数,有点不同,因为3个数有可能是一样的,这样查起来会有问题,所以先排序,处理了
: 特殊的有2个数重复,或者三个数重复的情况,再查 sum - a[i] - a[j]是不是在,复杂读
: 是O(N^2)
: k个数就更复杂了,复杂度接近brute force 复杂度O(N^(k-1))
| p********7
发帖数: 549 | 5 这个办法好
【在 d*****t 的大作中提到】
: 类似楼上，但是用递归。
: 两个数，查sum-a[i]，在HASHTABLE里就返回TRUE，不在就添加。
: 三个数，从数组中取出a[j],和数组最后一位a[N-1]交换位置。sum' = sum - a[N]，然
: 后对数组的a[0]~a[N-2]位，换两个数求和处理。
: 比较直观，但是空间复杂性比较大
| t******h
发帖数: 120 | 6
刚看到careercup上的一个类似的题 输入group的size 计算size个数的和是指定的和
比如输入size=3 total=0 找出数组3个数的和为0
我想如果用递归的话
两个数可以再进行一次类似的递归 size=1了
这个时候就是找出数组剩下的元素中 是否含total了
不知道这样行不行 这样就不用建hash table了
【在 d*****t 的大作中提到】
: 类似楼上，但是用递归。
: 两个数，查sum-a[i]，在HASHTABLE里就返回TRUE，不在就添加。
: 三个数，从数组中取出a[j],和数组最后一位a[N-1]交换位置。sum' = sum - a[N]，然
: 后对数组的a[0]~a[N-2]位，换两个数求和处理。
: 比较直观，但是空间复杂性比较大
| A*********r
发帖数: 564 | 7
是 sum' = sum - a[N－１]吧？
【在 d*****t 的大作中提到】
: 类似楼上，但是用递归。
: 两个数，查sum-a[i]，在HASHTABLE里就返回TRUE，不在就添加。
: 三个数，从数组中取出a[j],和数组最后一位a[N-1]交换位置。sum' = sum - a[N]，然
: 后对数组的a[0]~a[N-2]位，换两个数求和处理。
: 比较直观，但是空间复杂性比较大
|
|
