P*******b
发帖数: 1001 | 1 Given an integer array, design an algorithm to find the three indexes whose
sum is equal to a given sum k. |
I**A
发帖数: 2345 | 2 http://www.mitbbs.com/article_t/JobHunting/31654131.html
whose
【在 P*******b 的大作中提到】
: Given an integer array, design an algorithm to find the three indexes whose
: sum is equal to a given sum k.
|
P*******b
发帖数: 1001 | 3 thanks,
是这样吗？
bool ThreeSum(vector nums)
{
std::sort(nums.begin(), nums.end());
for (size_t i = 0; i < nums.size(); i++)
{
size_t j = 0;
size_t k = nums.size() - 1;
while ( j < k )
{
int result = nums[j] + nums[k] - nums[i];
if ( (result < 0) || (i == j) )
j++;
else if ( (result > 0) || (i == k) )
k--;
else
return true;
}
}
return false;
【在 I**A 的大作中提到】
: http://www.mitbbs.com/article_t/JobHunting/31654131.html
:
: whose
|
s*********t
发帖数: 1663 | 4 只要找一组吗？多组考虑不？
whose
【在 P*******b 的大作中提到】
: Given an integer array, design an algorithm to find the three indexes whose
: sum is equal to a given sum k.
|
s*********t
发帖数: 1663 | 5 我也写一个，欢迎大牛们拍砖。
std::vector threeKids(std::vector& arr, int n)
{
std::vector ret;
std::map > S1;
std::map > S2;
std::map >::iterator t;
for(size_t i=0; i
for(t = S2.begin(); t != S2.end(); t++ ){
if( t->first + arr[i] == n){
for(size_t j=0; jsecond.size(); j++)
ret.push_back( t->se
【在 P*******b 的大作中提到】
: Given an integer array, design an algorithm to find the three indexes whose
: sum is equal to a given sum k.
|
s*********t
发帖数: 1663 | 6 为啥return了bool?
【在 P*******b 的大作中提到】
: thanks,
: 是这样吗？
: bool ThreeSum(vector nums)
: {
: std::sort(nums.begin(), nums.end());
: for (size_t i = 0; i < nums.size(); i++)
: {
: size_t j = 0;
: size_t k = nums.size() - 1;
: while ( j < k )
|
I**A
发帖数: 2345 | 7 你写的这个好像是别人的方法，不记得了
你的问题，要求返回的是indexes or values or a simple true or false?
一般来说，是要找values或者是true or false
要是找index的话我觉得要额外做一些工作。。
我自己的方法是这样的
我们知道，用hashtable辅助，我们就可以找出两个数sum to a target in O(n).
when we want to find 3 values, we can do following
for each target-a[i], we try to see whether there are two numbers in the
array(excluding the ith one) their sum is target-a[i]..
【在 P*******b 的大作中提到】
: thanks,
: 是这样吗？
: bool ThreeSum(vector nums)
: {
: std::sort(nums.begin(), nums.end());
: for (size_t i = 0; i < nums.size(); i++)
: {
: size_t j = 0;
: size_t k = nums.size() - 1;
: while ( j < k )
|
