s***b
发帖数: 139 | 1 下面的程序如果用了注释部分，对于相等的key的处理就有错，如果不用注释部分，就
没错，不知道哪位大牛能解释下为什么啊？谢谢
Ex: 比如array = [2,1,9,4,4,56,90,3], target = 8,正确输出应该是4,5
如果定义hash table是用的是：table[numbers[i]] = i 那就能正确输出
如果定义用的是：table.insert(std::make_pair(numbers[i], i)); 那就
会输出4,4
对此十分不理解啊，不是同样的插入么？unordered_map是怎么处理key相等的状况的，
一般来说key不是unique的么？万分感谢啊！！！
class Solution {
public:
std::vector twoSum(std::vector &numbers, int target) {
std::vector result;
std::unordered_map table;
for(unsigned int i = 0; i < numbers.size(); i++) {
table[numbers[i]] = i;
// table.insert(std::make_pair(numbers[i], i));
}
for(unsigned int i = 0; i < numbers.size(); i++) {
if(table.find(target - numbers[i]) != table.end()) {
unsigned int j = table[target - numbers[i]];
if(i < j) {
result.push_back(i+1);
result.push_back(j+1);
}
else {
result.push_back(j+1);
result.push_back(i+1);
}
return result;
}
}
}
}; | k*******q
发帖数: 5493 | 2 先排序，然后双指针，一头一尾开始找
【在 s***b 的大作中提到】
: 下面的程序如果用了注释部分，对于相等的key的处理就有错，如果不用注释部分，就
: 没错，不知道哪位大牛能解释下为什么啊？谢谢
: Ex: 比如array = [2,1,9,4,4,56,90,3], target = 8,正确输出应该是4,5
: 如果定义hash table是用的是：table[numbers[i]] = i 那就能正确输出
: 如果定义用的是：table.insert(std::make_pair(numbers[i], i)); 那就
: 会输出4,4
: 对此十分不理解啊，不是同样的插入么？unordered_map是怎么处理key相等的状况的，
: 一般来说key不是unique的么？万分感谢啊！！！
: class Solution {
: public:
| s***b
发帖数: 139 | 3 可是排序时间复杂度就涨了，变成O(n log(n))了，用hash table只有O(n) | r*********n
发帖数: 4553 | 4 应该用unordered_multimap吧
比如array = [2,1,9,4,4,56,90,3], target = 8,正确输出应该是4,5
正确输出是3,4吧，index从0开始。你有2个4，用unordered_map，就相当于只有一个4
，你能成功，其实是因为8-4=4，你用了同一个元素两次。 | s***b
发帖数: 139 | 5 多谢多谢！！！
题目要求从1开始计数，输出结果每个都+1,其实就是3,4
我的困惑是在用unordered_map时，下面两行应该产生同样的效果
table[numbers[i]] = i;
table.insert(std::make_pair(numbers[i], i));
可是第一个的结果就是正确的，第二个就不对，这是为什么？
感觉好像确实应该用unordered_multimap，在unordered_map里key应该是unique的 | r*********n
发帖数: 4553 | 6
这两行代码结果不一样就是因为unordered_map的key是unique的
你有两个4，一个在i = 3，一个在i=4
你用table[numbers[i]] = i，最后table[4] = 4
但是你用table.insert(std::make_pair(numbers[i], i))，最后table[4]=
3，因为第二个insert是无效的，你已经有了一个table[4]
【在 s***b 的大作中提到】
: 多谢多谢！！！
: 题目要求从1开始计数，输出结果每个都+1,其实就是3,4
: 我的困惑是在用unordered_map时，下面两行应该产生同样的效果
: table[numbers[i]] = i;
: table.insert(std::make_pair(numbers[i], i));
: 可是第一个的结果就是正确的，第二个就不对，这是为什么？
: 感觉好像确实应该用unordered_multimap，在unordered_map里key应该是unique的
| s***b
发帖数: 139 | |
|
