e***n
发帖数: 42 | 1 第一遍扫描array用hashmap存array[i]，
第二遍扫描找出hashmap（target - array[i]）
但是如果遇到重复多次的数（如下例程 x=5）且x+x=target=10， C++ 的hashtable （
map) 就只存第一次出现的x 请问有什么办法解决？
#include | p*****2
发帖数: 21240 | 2 这不就是two sum吗？
用两个pointer前后往里移动。
如果用hashtable存一下数字出现的次数。 | w****o
发帖数: 2260 | 3 北京二爷，
能说说如何“用hashtable存一下数字出现的次数”？
存这个信息有什么用？
【在 p*****2 的大作中提到】
: 这不就是two sum吗？
: 用两个pointer前后往里移动。
: 如果用hashtable存一下数字出现的次数。
| p*****2
发帖数: 21240 | 4
判断重复。
比如你有一个5, sum=10, 你要知道你有几个5, 如果一个5就不可以。两个就可以。
【在 w****o 的大作中提到】
: 北京二爷，
: 能说说如何“用hashtable存一下数字出现的次数”？
: 存这个信息有什么用？
| z*********8
发帖数: 2070 | 5 求两数的和 没必要吧
如果只有一个5， 处理到这个5的时候 hashtable里面还没有这个值
三数以上就需要了
【在 p*****2 的大作中提到】
:
: 判断重复。
: 比如你有一个5, sum=10, 你要知道你有几个5, 如果一个5就不可以。两个就可以。
| G******e
发帖数: 229 | 6 How about using multimap? | p*****2
发帖数: 21240 | 7 Shi
求两数的和 没必要吧如果只有一个5， 处理到这个5的时候 hashtable里面还没有这个
值三数以上就需要了
★ Sent from iPhone App: iReader Mitbbs Lite 7.52
【在 z*********8 的大作中提到】
: 求两数的和 没必要吧
: 如果只有一个5， 处理到这个5的时候 hashtable里面还没有这个值
: 三数以上就需要了
| f******c
发帖数: 80 | 8 这不是two sum吗？不用什么hashtable，直接先排下序，然后两个指针往中间走，两个
数和等于target，两个指针就同时往中间走一步，不等于target，相应的一个指针走一
步？ | G******e
发帖数: 229 | 9 If you sort first, the time complexity would be O(nlogn). Hashtable only
requires O(n) (linear time) in average case.
【在 f******c 的大作中提到】
: 这不是two sum吗？不用什么hashtable，直接先排下序，然后两个指针往中间走，两个
: 数和等于target，两个指针就同时往中间走一步，不等于target，相应的一个指针走一
: 步？
| e***n
发帖数: 42 | 10 搞定.用了multimap 和两个iterator.
#include | | | k******I
发帖数: 238 | 11 你这个复杂度多少？ While 里面套loop...
【在 e***n 的大作中提到】
: 搞定.用了multimap 和两个iterator.
: #include
| g****v
发帖数: 971 | | k***g
发帖数: 166 | 13 弱人路过，用的是楼上说的两个指针往中间走的办法
#include
using namespace std;
void find2sum(int a[], int size, int target)
{
if (size<2)
return;
for (int i=0, j=size-1; i
int sum = a[i]+a[j];
if (sum == target) {
cout<
i++; j--;
} else if (sum > target) {
j--;
} else if (sum < target) {
i++;
}
}
}
int main(int argc, char* argv[])
{
//int a[] = {1, 4, 5, 5, 5, 5, 6, 7, 8, 9, 11, 13, 15};
//int a[] = {1, 4, 5, 5, 5, 5, 5, 6, 7, 8, 9, 11, 13, 15};
// int a[] = {1, 4, 4, 5, 5, 5, 5, 5, 6, 7, 8, 9, 11, 13, 15};
int a[] = {5, 5, 5};
find2sum(a, sizeof(a)/sizeof(int), 10);
return 0;
} | q***y
发帖数: 236 | 14 map里存出现次数，每用掉一个数就把对应次数减1，减为0时从map中删除。 | e***n
发帖数: 42 | 15 复杂度O(n)
因为里面的for loop最多只会执行两次（只要找到不是本身的另一个等值元素就break）
【在 k******I 的大作中提到】
: 你这个复杂度多少？ While 里面套loop...
| i*********7
发帖数: 348 | 16 压根不用扫两次。扫一次就够了，一边扫一边建hash_map一边对比。 | b***d
发帖数: 87 | 17 这里9+1，1+9要输出两次？神马情况？
正确输出：(5+5应出现两次）
9+1
6+4
5+5
5+5
4+6
1+9
【在 e***n 的大作中提到】
: 复杂度O(n)
: 因为里面的for loop最多只会执行两次（只要找到不是本身的另一个等值元素就break）
|
|
