chapter_searching/replace_linear_by_hashing/

[giscus[bot]]

chapter_searching/replace_linear_by_hashing/

一本动画图解、能运行、可提问的数据结构与算法入门书

https://www.hello-algo.com/chapter_searching/replace_linear_by_hashing/

[hatkd]

很谢谢作者

[krahets]

感谢鼓励！

[Wonderdch]

建议将“两数之和”的题目也放进来，免得跳转过去看分心

[JJLAAA]

本书的定位应该不是那种带着刷算法的，为了保持简洁，放个链接应该够了

[FangYuan33]

我觉得应该放进来，至少我读到这儿的时候在下意识的找题干，如果是点击链接还是觉得有些麻烦

[krahets]

🫡收到已加～

[paulxu001]

dic.containsKey函数的最差时间复杂度不是O(1)

[krahets]

是的，在某些条件下会劣化～但在做题时，我们一般会认为哈希表时间复杂度 O(1) 。

[lirantongxue]

元旦过后,遇到最好的礼物。我真心觉得这么好的入门工具书,首先应该让人读的尽兴。而不是半遮半掩,我希望后面那些有规划没有写出来的内容抓紧和我们读者见面。否则很扫兴呀。

[krahets]

谢谢鼓励！在加紧更新，请再给我一些时间。PS：没有半遮半掩，感觉很努力地在写了哈哈

[xlcodes]

作者大大加油，算法小白一枚持续关注ing...

[Chilled-Coke]

为啥程序在C语言那一栏显示不了？

[krahets]

C 语言代码暂时还在测试，等测试好会加入～！

[Miyolovecode]

期待期待！！

[zh-h]

两数之和那道题，有点背单词 abandon 的感觉。

[krahets]

有那味了

[dengyunsheng250]

没有C的代码吗？

[krahets]

抱歉！ C 的代码还在翻译+测试中，可能暂时只能用 C++ 来代替

[Chilled-Coke]

作者大大加油！

[happykala]

作者你好，示例代码对于处理nums列表中存在多个满足两个数值之和为target的情况是不是解决不了呢？？

[krahets]

是的，这道题要求返回第一对即可

[TDB001]

// C++
vector vec {1, 2, 3, 4};
cout << twoSumBruteForce(vec, 5) << endl; // [0, 3]
cout << twoSumHashTable(vec, 5) << endl; // [1, 2]

// Swift
let nums = [1, 2, 3, 4]
print(twoSumBruteForce(nums: nums, target: 5)) // [0, 3]
print(twoSumHashTable(nums: nums, target: 5)) // [1, 2]

k神，两个方法结果不同，twoSumHashTable 这个取到的不是第1个下标。

[krahets]

这个没关系，题目只要求输出任一满足条件的组合即可。

由于两个方法的遍历方式不同，因此它们找到解的顺序是不同的。暴力法是普通的双层遍历，总会优先找到包含靠左边元素的组合。哈希表法是一次遍历，在你展示的示例中就会先找到 [1, 2] 这个组合。

[TDB001]

👌

[TangJun815]

测试了一下，还是需要具体问题具体分析，如下情况线性查找就比哈希好。

C#测试代码
//准备
var sw = new Stopwatch();
var nums = Enumerable.Range(1,int.MaxValue/2).ToArray();

//暴力枚举
sw.Start();
var s = twoSumBruteForce(nums, 999999999);
sw.Stop();
Console.WriteLine($"暴力枚举用时:{sw.Elapsed.TotalSeconds}秒");
foreach (var i in s)
{
	Console.WriteLine($"索引：{i}，值：{nums[i]}");
}

//辅助哈希
sw.Start();
var s2 = twoSumHashTable(nums, 999999999);
sw.Stop();
Console.WriteLine($"辅助哈希表用时:{sw.Elapsed.TotalSeconds}秒");
foreach (var i in s2)
{
	Console.WriteLine($"索引：{i}，值：{nums[i]}");
}

输出结果：
暴力枚举用时:1.7970771秒
索引：0，值：1
索引：999999997，值：999999998
辅助哈希表用时:51.2555588秒
索引：499999998，值：499999999
索引：499999999，值：500000000

[fiona-liu12]

如果能给出对应力扣上可以训练同类型的题目就好了

[krahets]

推荐这个题单

[Cupcc]

希望能添加相应题目的链接

[WheatJack]

https://leetcode.cn/problems/two-sum/

[newcakes]

@krahets佬，为什么C++哈希查找的算法时间复杂度是O(n)呀！在使用find()这个函数的时候不是需要遍历哈希表吗？时间复杂度是O(n),n次不就是O(n2)吗？
还是说哈希的find()函数的时间复杂度是O(1)。

[krahets]

unordered_map 是哈希表，它的 find() 的时间复杂度是 O(1) 哈

[newcakes]

好的，谢谢

[ChinaYong]

问一下，为什么要用诸如
Map<Integer, Integer> dic = new HashMap<>();
的语句啊？相比
HashMap<Integer, Integer> dic = new HashMap<>();
有什么优点吗？

[krahets]

好问题！使用接口类型作为引用类型可以使代码的意图更加清晰，它表明我们只打算使用接口提供的方法，而不是特定实现的额外方法。

从逻辑上讲，我们想用的是一个 Map 来实现映射功能，而出于效率考虑，使用 HashMap 作为这个 Map 的实现。

[HangSeven]

这是不是就是多态，编译看左边，运行看右边

[HuaWang135608]

因为 Map 是接口，HashMap 是 Map 接口的实现类；这个就是面向接口编程的习惯，感兴趣可以看一下设计模式中的开闭原则和依赖倒置原则。

[Terran0629]

leetcode第一题哈哈哈哈大家的入门题

[qw124341789]

要是力扣太难去刷PTA吧

[cy-by-side]

为什么暴力时不先把target - nums[i]提出来? ns级优化

[Lirous587]

怎么个优化法？提出来还不是要再来一个循环吗

[RENHJa]

请问，c语言暴力枚举中函数第四个参数int *returnSize是什么作用？

[krahets]

用于记录 res 的长度，函数返回后需要用到

[RENHJa]

那为什么记录res的长度是 int* 类型而不是 int 型呢？

[cy-by-side]

可能是int *改变实参,int 只能改变形参

[Lirous587]

因为返回数组之后你需要一个数组的lens 数组不知道lens的话这个数组也就没意义了 而c里面计算lens是很不方便的 所以直接传一个int* returnSize就很方便了 或者你可以传一个结构体的指针 里面带有
typedef struct {
int returnSize;
int * res ;
} ReturnData;
反正数组必须要有它的lens 至于方法无所谓的

[Tiro-Wang]

c#中这段代码

        if (dic.ContainsKey(target - nums[i])) {
            return [dic[target - nums[i]], i];
        }
        dic.Add(nums[i], i);

改变一下顺序也是可以的，

        dic.Add(nums[i], i);
        if (dic.ContainsKey(target - nums[i])) {
            return [dic[target - nums[i]], i];
        }

目前想不懂源代码的写法是不是更有优势呢。

[KLYkl]

如果你改了，刚刚好遇到一个索引的数是target的两倍，但如果是题目要求不能是数组的同一个索引，请问阁下如何应对？哈哈哈

[KLYkl]

而根据作者给出的解法，默认是不能是同一个数组索引的元素。

[Re-xiguan]

/* 方法二：辅助哈希表 */
vector<int> twoSumHashTable(vector<int> &nums, int target) {
    int size = nums.size();
    // 辅助哈希表，空间复杂度为 O(n)
    unordered_map<int, int> dic;
    // 单层循环，时间复杂度为 O(n)
    for (int i = 0; i < size; i++) {
        if (dic.find(target - nums[i]) != dic.end()) {
            return {dic[target - nums[i]], i};
        }
        dic.emplace(nums[i], i);
    }
    return {};
}

辅助哈希表中的查找和维护时间复杂度不是log（n）吗

[Re-xiguan]

借助哈希表搜索时间复杂度为什么会降到n啊

[wqc18737346950]

我的理解是，hash表中增删改操作时间复杂度都是O(1)，然后只有一层循环，所以是O(n)

[1435646097]

是的，hash表中增删改操作时间复杂度都是O(1)，只用管外层循环就可以了

[sevenzard]

K大，举一反三，假定题中的两个元素可以重复，例如：

    nums = [2, 7, 11, 15]
    target = 14

可以返回 [1, 1]作为结果，两种解法该如何更改呢？

[krahets]

Hi，由于是两个元素，因此遍历每个元素 n 试一下 n*n 是否可以就行了，仍然是一个 O(n) 的操作

[KLYkl]

将dic插入的操作位置放在if判断之前即可。

[niyongsheng]

补充一个排序+双指针策略，空间复杂度O(1) 时间复杂度O(nlogn)

int[] findTwoSum(int[] nums, int target) {
    Arrays.sort(nums); // 对数组排序
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return new int[]{left, right};
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return null;

[xbuffer]

你的算法前提是数组要有序

[xbuffer]

数组排序的时间复杂度也要加上才行

[niyongsheng]

根据大 O 符号的定义，它描述算法运行时间的上限。在多个复杂度项相加的情况下，通常只保留最高阶项。

O(n log n)(排序) + O(n)(双指针)由于排序是主要的复杂度，因此总的时间复杂度是 O(n log n)

不过排序后拿到索引已经不是原数组的索引了，可以创建一个辅助二维数组来存储元素和原始索引，在创建的同时使用归并排序。

• 时间复杂度：O(n log n)
• 空间复杂度：O(log n)

还是哈希表策略更优，只是提供一个思路；

[lt421]

001 两数之和！

[daLuyu]

two_sum.c中针对uthash.h提供的函数的使用是否有错误？查阅文档，似乎HASH_ADD_INT（）等接收的第一个参数均为指向HashTable指针的指针

[LifeIsTerrible]

nice

[snowliy]

发现一个小bug，图10-9的“7”行加法算错了，“7+15”=22不是23😄

[krahets]

谢谢指正！