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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : o(n)就行了... : 提示:从左往右+从右往左
| r****7 发帖数: 2282 | 6 我觉得不一定啊,感觉sort过之后是不是可以有的case给skip掉呢?
is
【在 l******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 怎么个从左往右从右往左啊。。。怎么想都不对啊 : 这array也没说是sorted
| n*******s 发帖数: 17267 | 8 sort完了变成1234789, 然后找A+B=C+D并且满足和在5(1+4)和13(4+9)之间的?
【在 r****7 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 没有sort倒是可以sort,cheaper than n^2,然后用类似2sum的算法么?可是没有固定 : 的target,貌似也还是要遍历很多种可能。
| l******n 发帖数: 9344 | 9 如果数组有重复的,怎么办?
【在 n*******s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : o(n)就行了... : 提示:从左往右+从右往左
| r****7 发帖数: 2282 | 17 我觉得不一定啊,感觉sort过之后是不是可以有的case给skip掉呢?
is
【在 l******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 怎么个从左往右从右往左啊。。。怎么想都不对啊 : 这array也没说是sorted
| n*******s 发帖数: 17267 | 19 sort完了变成1234789, 然后找A+B=C+D并且满足和在5(1+4)和13(4+9)之间的?
【在 r****7 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 没有sort倒是可以sort,cheaper than n^2,然后用类似2sum的算法么?可是没有固定 : 的target,貌似也还是要遍历很多种可能。
| l******n 发帖数: 9344 | 20 如果数组有重复的,怎么办?
【在 n*******s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 | |
|