r****7
发帖数: 2282 | 1 You're given an array of integers(eg [3,4,7,1,2,9,8]) Find the index of
values that satisfy A+B = C + D, where A,B,C & D are integers values in the
array.
Eg: Given [3,4,7,1,2,9,8] array
The following
3+7 = 1+ 9 satisfies A+B=C+D
so print (0,2,3,5) | l******n
发帖数: 9344 | 2 No! if you just want to find out all the possible sums, it is O(n^2), it is
hard bottom.
the
【在 r****7 的大作中提到】
: You're given an array of integers(eg [3,4,7,1,2,9,8]) Find the index of
: values that satisfy A+B = C + D, where A,B,C & D are integers values in the
: array.
: Eg: Given [3,4,7,1,2,9,8] array
: The following
: 3+7 = 1+ 9 satisfies A+B=C+D
: so print (0,2,3,5)
| d*******i
发帖数: 31 | | y****t
发帖数: 23 | | l*****n
发帖数: 246 | 5 怎么个从左往右从右往左啊。。。怎么想都不对啊
这array也没说是sorted
【在 y****t 的大作中提到】
: o(n)就行了...
: 提示：从左往右+从右往左
| r****7
发帖数: 2282 | 6 我觉得不一定啊，感觉sort过之后是不是可以有的case给skip掉呢？
is
【在 l******n 的大作中提到】
: No! if you just want to find out all the possible sums, it is O(n^2), it is
: hard bottom.
:
: the
| r****7
发帖数: 2282 | 7 没有sort倒是可以sort，cheaper than n^2，然后用类似2sum的算法么？可是没有固定
的target，貌似也还是要遍历很多种可能。
【在 l*****n 的大作中提到】
: 怎么个从左往右从右往左啊。。。怎么想都不对啊
: 这array也没说是sorted
| n*******s
发帖数: 17267 | 8 sort完了变成1234789， 然后找A+B=C+D并且满足和在5(1+4)和13(4+9)之间的？
【在 r****7 的大作中提到】
: 没有sort倒是可以sort，cheaper than n^2，然后用类似2sum的算法么？可是没有固定
: 的target，貌似也还是要遍历很多种可能。
| l******n
发帖数: 9344 | 9 如果数组有重复的，怎么办？
【在 n*******s 的大作中提到】
: sort完了变成1234789， 然后找A+B=C+D并且满足和在5(1+4)和13(4+9)之间的？
| x*******9
发帖数: 138 | 10 如果用指针来找的话，至少要确定三个指针才能推出第四个。所以我觉得即使数组是有
序的，用双（多）指针法也是不可行的。
等大神解答。 | | | d**********6
发帖数: 4434 | 11 就算把范围cut了，还是要计算比如n/2或者n/4内所有数字的组合，结果还是O(n^2)
【在 n*******s 的大作中提到】
: sort完了变成1234789， 然后找A+B=C+D并且满足和在5(1+4)和13(4+9)之间的？
| r****7
发帖数: 2282 | 12 You're given an array of integers(eg [3,4,7,1,2,9,8]) Find the index of
values that satisfy A+B = C + D, where A,B,C & D are integers values in the
array.
Eg: Given [3,4,7,1,2,9,8] array
The following
3+7 = 1+ 9 satisfies A+B=C+D
so print (0,2,3,5) | l******n
发帖数: 9344 | 13 No! if you just want to find out all the possible sums, it is O(n^2), it is
hard bottom.
the
【在 r****7 的大作中提到】
: You're given an array of integers(eg [3,4,7,1,2,9,8]) Find the index of
: values that satisfy A+B = C + D, where A,B,C & D are integers values in the
: array.
: Eg: Given [3,4,7,1,2,9,8] array
: The following
: 3+7 = 1+ 9 satisfies A+B=C+D
: so print (0,2,3,5)
| d*******i
发帖数: 31 | | y****t
发帖数: 23 | 15 o(n)就行了...
提示：从左往右+从右往左 | l*****n
发帖数: 246 | 16 怎么个从左往右从右往左啊。。。怎么想都不对啊
这array也没说是sorted
【在 y****t 的大作中提到】
: o(n)就行了...
: 提示：从左往右+从右往左
| r****7
发帖数: 2282 | 17 我觉得不一定啊，感觉sort过之后是不是可以有的case给skip掉呢？
is
【在 l******n 的大作中提到】
: No! if you just want to find out all the possible sums, it is O(n^2), it is
: hard bottom.
:
: the
| r****7
发帖数: 2282 | 18 没有sort倒是可以sort，cheaper than n^2，然后用类似2sum的算法么？可是没有固定
的target，貌似也还是要遍历很多种可能。
【在 l*****n 的大作中提到】
: 怎么个从左往右从右往左啊。。。怎么想都不对啊
: 这array也没说是sorted
| n*******s
发帖数: 17267 | 19 sort完了变成1234789， 然后找A+B=C+D并且满足和在5(1+4)和13(4+9)之间的？
【在 r****7 的大作中提到】
: 没有sort倒是可以sort，cheaper than n^2，然后用类似2sum的算法么？可是没有固定
: 的target，貌似也还是要遍历很多种可能。
| l******n
发帖数: 9344 | 20 如果数组有重复的，怎么办？
【在 n*******s 的大作中提到】
: sort完了变成1234789， 然后找A+B=C+D并且满足和在5(1+4)和13(4+9)之间的？
| | | x*******9
发帖数: 138 | 21 如果用指针来找的话，至少要确定三个指针才能推出第四个。所以我觉得即使数组是有
序的，用双（多）指针法也是不可行的。
等大神解答。 | d**********6
发帖数: 4434 | 22 就算把范围cut了，还是要计算比如n/2或者n/4内所有数字的组合，结果还是O(n^2)
【在 n*******s 的大作中提到】
: sort完了变成1234789， 然后找A+B=C+D并且满足和在5(1+4)和13(4+9)之间的？
| a*********0
发帖数: 2727 | 23 vector> 2sumSum(vector& a)
{
vector> res;
size_t n=a.size();
if(n<4) return res;
unordered_map>> umap;
for(size_t i=0;i
for(size_t j=i+1;j
int sum=a[i]+a[j];
if(umap.find(sum)!=umap.end()) {
for(auto e: umap[sum]){
res.push_back({i,j, e.first, e.second});
}
}
umap[sum].push_back(make_pair(i, j));
}
}
return res;
} | p***m
发帖数: 387 | 24 两层循环是无论如何都省不了的，这就是O(n^2)了
the
【在 r****7 的大作中提到】
: You're given an array of integers(eg [3,4,7,1,2,9,8]) Find the index of
: values that satisfy A+B = C + D, where A,B,C & D are integers values in the
: array.
: Eg: Given [3,4,7,1,2,9,8] array
: The following
: 3+7 = 1+ 9 satisfies A+B=C+D
: so print (0,2,3,5)
| h****3
发帖数: 89 | 25 举个极端的例子，如果array中所有元素都相同，那么n^2是无法避免的 | m*******n
发帖数: 47 | |
|
