w***y
发帖数: 6251 | 1 第4版里面的一道题目
19.11 Design an algorithm to find all pairs of integers within an array
which sum to a specified value.
解法不复杂, 不过看样子是不用考虑array里面有重复数字的. 这样条件就简单很多-
-当然这个题如果要考虑重复数字, 意义也不大,完全就是为了题目更繁琐一点hehe
但是如果题目没有明确说, 怎么知道要不要考虑有重复数字的? | w****x
发帖数: 2483 | 2
多-
对两边夹的那个算法做一点修改.
把之前match的pair用hash存起来, 之后遍历的每个数字检查hash table, 如果
match的话就直接i++或j--(跳过)
【在 w***y 的大作中提到】
: 第4版里面的一道题目
: 19.11 Design an algorithm to find all pairs of integers within an array
: which sum to a specified value.
: 解法不复杂, 不过看样子是不用考虑array里面有重复数字的. 这样条件就简单很多-
: -当然这个题如果要考虑重复数字, 意义也不大,完全就是为了题目更繁琐一点hehe
: 但是如果题目没有明确说, 怎么知道要不要考虑有重复数字的?
| w***y
发帖数: 6251 | 3 第4版里面的一道题目
19.11 Design an algorithm to find all pairs of integers within an array
which sum to a specified value.
解法不复杂, 不过看样子是不用考虑array里面有重复数字的. 这样条件就简单很多-
-当然这个题如果要考虑重复数字, 意义也不大,完全就是为了题目更繁琐一点hehe
但是如果题目没有明确说, 怎么知道要不要考虑有重复数字的? | w****x
发帖数: 2483 | 4
多-
对两边夹的那个算法做一点修改.
把之前match的pair用hash存起来, 之后遍历的每个数字检查hash table, 如果
match的话就直接i++或j--(跳过)
【在 w***y 的大作中提到】
: 第4版里面的一道题目
: 19.11 Design an algorithm to find all pairs of integers within an array
: which sum to a specified value.
: 解法不复杂, 不过看样子是不用考虑array里面有重复数字的. 这样条件就简单很多-
: -当然这个题如果要考虑重复数字, 意义也不大,完全就是为了题目更繁琐一点hehe
: 但是如果题目没有明确说, 怎么知道要不要考虑有重复数字的?
| t*******e
发帖数: 274 | 5 我用hashtable做的话，怎么避免输出(3,4),(4,3），而只输出一组（假设sum = 7) | t*******e
发帖数: 274 | 6 如果用hashtable的话，如何避免重复输出，例如：sum=7,输出（3，4），（4，3）？ | d*******3
发帖数: 58 | 7 把较小的一个值做为key,(3,4),（4，3）不就是同一个pair了么， | N*****Z
发帖数: 70 | 8 难道居然不是先做sort？
【在 t*******e 的大作中提到】
: 我用hashtable做的话，怎么避免输出(3,4),(4,3），而只输出一组（假设sum = 7)
| t*******e
发帖数: 274 | 9
不是太明白你的意思，能具体说一下么？
【在 d*******3 的大作中提到】
: 把较小的一个值做为key,(3,4),（4，3）不就是同一个pair了么，
| Z**********4
发帖数: 528 | 10 这题不用把一个pair都存 遇到3就存4 遇到4就存3好了 如果要避免重复就这样：遇到3
的时候存4 然后遇到4的时候说明找到一对了 这个时候把3也存进去 下次不管遇到3还
是4都不管 整个过程不用sort
不是太明白你的意思，能具体说一下么？
【在 t*******e 的大作中提到】
:
: 不是太明白你的意思，能具体说一下么？
| t*******e
发帖数: 274 | 11 我想我的问题是在于输出的时候，按你的意思，把（3，4），（4，3）都存在
hashtable中，如果我想只输出其中一组结果，该怎么做呢？ | d*******3
发帖数: 58 | 12 Zhuimeng1314说的对，就是这个意思，这是hash的解法。（3，4），（4，3）不需要都
存，只存一个3就行了
敲了下代码，不知道有木有bug...
vector > twoSum(vector& num,int target)
{
vector >ans;
hash_map num_map;
hash_map pair_map;
typedef pair IntPair;
for(int i=0;i
num_map.insert(IntPair(num[i],1));
for(int i=0;i
{
if(num_map.find(target-num[i])!=num_map.end())//for num[i],exist
target-num[i]
{
int smaller_num=min(num[i],target-num[i]);
if(pair_map.find(smaller_num)==pair_map.end())//pair not found
{
vector tmp;
tmp.push_back(num[i]);
tmp.push_back(target-num[i]);
ans.push_back(tmp);
pair_map.insert(IntPair(smaller_num,1));
}
}
}
return ans;
}
test case1:{3,4,9,5,2,5,5,4,3}，target=7
output:{3,4},{2,5}
test case2:{3,4,3,2,3,2,3,4,4},target=6
output:{3,3},{4,2}
如果sort的话，个人感觉用wwwyhx说的那种两边夹的方法，就不需要hash了，这不是
3sum的简单版
么？ | Z**********4
发帖数: 528 | 13 我的意思是不用整个pair用一个hash map就可以了。不过我想做点改动 利用hash里面
key对应的value来标志对（3，4）已经找过了，下次不论是（4，3）还是（3，4）都视
而不见。
hash_map hash;
vector::iterator iter;
vector result;
for(iter = array.begin(); iter!= array.end(); iter++){
if(hash.find(*iter) == hash.end() && hash.find(n-*iter) == hash.end(
)){
hash[n-*iter] = 1; //这是第一次遇见3的时候，存入 4->1
}
else if(hash[*iter]==1){ //发现hash里面有4，而且value是1 就算找到了
（3，4）
hash[*iter]=0; //将hash[*iter]置位成0这样下次无论是出现3或者4
都不会进入这个block因为只有hash对应的是1的时候才会进入
stringstream ss;
if(*iter<=n/2)
ss << *iter <<" and "<
else
ss << n-*iter <<" and "<<*iter<
result.push_back(ss.str());
}
}
【在 d*******3 的大作中提到】
: Zhuimeng1314说的对，就是这个意思，这是hash的解法。（3，4），（4，3）不需要都
: 存，只存一个3就行了
: 敲了下代码，不知道有木有bug...
: vector > twoSum(vector& num,int target)
: {
: vector >ans;
: hash_map num_map;
: hash_map pair_map;
: typedef pair IntPair;
: for(int i=0;i
|
|
