C***y 发帖数: 2546 | |
b******g 发帖数: 1721 | 2 那我就抛砖引玉了,针对3个数的。
1. 两个for-loops得到任意2个数的和,存在一个临时数组,tmp1. O(n^2)
2. sort (tmp1). O(nlogn)如果merge sort.
3. 再扫一遍原来数组,对于每个元素,a, search(-a) 在sorted tmp1. O(nlogn)
所以,O(n^2).
自我感觉,我们必须对所以pair的数进行判断,所以这就是最优化的算法。 |
y***d 发帖数: 2330 | 3 那个 sort 是(n^2)log(n^2)
【在 b******g 的大作中提到】 : 那我就抛砖引玉了,针对3个数的。 : 1. 两个for-loops得到任意2个数的和,存在一个临时数组,tmp1. O(n^2) : 2. sort (tmp1). O(nlogn)如果merge sort. : 3. 再扫一遍原来数组,对于每个元素,a, search(-a) 在sorted tmp1. O(nlogn) : 所以,O(n^2). : 自我感觉,我们必须对所以pair的数进行判断,所以这就是最优化的算法。
|
C***y 发帖数: 2546 | 4 稍微改进一下:
1.直接sort原来的数组
2.从第一个元素开始,扫描当前元素a[i]后面的subarray (a[i+1] to a[n-1],找和为
-a[i]的pair,因为是sorted,所以可以O(n-i)找到
复杂度应该还是O(n^2)
【在 b******g 的大作中提到】 : 那我就抛砖引玉了,针对3个数的。 : 1. 两个for-loops得到任意2个数的和,存在一个临时数组,tmp1. O(n^2) : 2. sort (tmp1). O(nlogn)如果merge sort. : 3. 再扫一遍原来数组,对于每个元素,a, search(-a) 在sorted tmp1. O(nlogn) : 所以,O(n^2). : 自我感觉,我们必须对所以pair的数进行判断,所以这就是最优化的算法。
|
S*******0 发帖数: 198 | 5 不如直接把tmp1放在hash table里,scan原来数组,看-a是否在table里
【在 b******g 的大作中提到】 : 那我就抛砖引玉了,针对3个数的。 : 1. 两个for-loops得到任意2个数的和,存在一个临时数组,tmp1. O(n^2) : 2. sort (tmp1). O(nlogn)如果merge sort. : 3. 再扫一遍原来数组,对于每个元素,a, search(-a) 在sorted tmp1. O(nlogn) : 所以,O(n^2). : 自我感觉,我们必须对所以pair的数进行判断,所以这就是最优化的算法。
|
b******g 发帖数: 1721 | 6 是nlogn吧,tmp1的size仍然是等于原始数组的长度,n。
【在 y***d 的大作中提到】 : 那个 sort 是(n^2)log(n^2)
|
w****x 发帖数: 2483 | |
m*****k 发帖数: 731 | 8 Nice!
【在 C***y 的大作中提到】 : 稍微改进一下: : 1.直接sort原来的数组 : 2.从第一个元素开始,扫描当前元素a[i]后面的subarray (a[i+1] to a[n-1],找和为 : -a[i]的pair,因为是sorted,所以可以O(n-i)找到 : 复杂度应该还是O(n^2)
|
q***0 发帖数: 43 | 9 This is called the sub-set sum problem. |
b******g 发帖数: 1721 | 10 确实是O(n^2logn^2)
【在 w****x 的大作中提到】 : 那个sort的确是O(n^2 logn)
|
r****t 发帖数: 10904 | 11 这个办法也适合于 4 个数的,写成递归就行了。不知道复杂度多少?
【在 C***y 的大作中提到】 : 稍微改进一下: : 1.直接sort原来的数组 : 2.从第一个元素开始,扫描当前元素a[i]后面的subarray (a[i+1] to a[n-1],找和为 : -a[i]的pair,因为是sorted,所以可以O(n-i)找到 : 复杂度应该还是O(n^2)
|