b******i
发帖数: 914 | 1 1. 3个长度一样的array a1, a2, a3, 找出所有 A + B = C 的组合，A在a1里，B在a2
，C在a3里；扩展到4个数组 a2, a2, a3, a4，找出A+B+C=D的组合。。 然后扩展到n各
数组；
题目没说用不用hashtable，以及有没有重复的数。
请问大家分析分析怎么做的最简单？谢谢了！ |
h****3
发帖数: 89 | 2 想了很久也没什么好想法， 哪位大神有好方法分享一下吗 |
P******r
发帖数: 1342 | |
s****a
发帖数: 501 | |
l******s
发帖数: 3045 | 5 先都排序，可以确定An的值域，减少些循环.在每个维度上找数逼近时用二分查找法。O
(n*logn)?
抛砖。 |
b******i
发帖数: 914 | 6 请问，确定An的值域，减少循环，能不能展开来说说？
这题一个straightforward的方法（针对三个数组）就是先对每个数组排序，然后遍历C
中每一个元素，每个iteration用两个指针，一个指向A的头，一个指向B的尾，逐渐逼
近看能不能达到A+B=C。
这个复杂度是O（N^2）。
。O
【在 l******s 的大作中提到】
: 先都排序，可以确定An的值域，减少些循环.在每个维度上找数逼近时用二分查找法。O
: (n*logn)?
: 抛砖。
|
l******s
发帖数: 3045 | 7 sum2的情况下我的方法是根据A作O(n)循环，B上作二分查找的O(logn)
历C
【在 b******i 的大作中提到】
: 请问，确定An的值域，减少循环，能不能展开来说说？
: 这题一个straightforward的方法（针对三个数组）就是先对每个数组排序，然后遍历C
: 中每一个元素，每个iteration用两个指针，一个指向A的头，一个指向B的尾，逐渐逼
: 近看能不能达到A+B=C。
: 这个复杂度是O（N^2）。
:
: 。O
|
b******i
发帖数: 914 | 8 请问你说的sum2的情况是什么意思？我原题只有A+B=C或者A+B+C＝D
【在 l******s 的大作中提到】
: sum2的情况下我的方法是根据A作O(n)循环，B上作二分查找的O(logn)
:
: 历C
|
n******n
发帖数: 12088 | 9 没必要钻牛角尖。题是做不完的
【在 b******i 的大作中提到】
: 请问你说的sum2的情况是什么意思？我原题只有A+B=C或者A+B+C＝D
|
l******s
发帖数: 3045 | 10 A+B=C
【在 b******i 的大作中提到】
: 请问你说的sum2的情况是什么意思？我原题只有A+B=C或者A+B+C＝D
|
T*****u
发帖数: 7103 | |
