[数据结构与算法] 代码随想录第六天

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 代码随想录第六天｜第三章哈希表II -> 正文阅读

[数据结构与算法]代码随想录第六天｜第三章哈希表II

#Java、#哈希表、#数组、#双指针

一、今日学习链接

? ? ? ? 1、1.?两数之和，文章链接，视频链接

? ? ? ? 2、454. 四数相加II，文章链接，视频链接

? ? ? ? 3、383. 赎金信，文章链接

? ? ? ? 4、15. 三数之和，文章链接，视频链接

? ? ? ? 5、18. 四数之和，文章链接，视频链接

二、理论知识

????????一般来说哈希表都是用来快速判断一个元素是否出现集合里。

????????对于哈希表，要知道哈希函数和哈希碰撞在哈希表中的作用.

????????哈希函数是把传入的key映射到符号表的索引上。

????????哈希碰撞处理有多个key映射到相同索引上时的情景，处理碰撞的普遍方式是拉链法和线性探测法。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

????????接下来是常见的三种哈希结构：

数组
set（集合）
map（映射）

? ? ? ? 数组作为哈希表：383.赎金信。使用map的空间消耗要比数组大一些，因为map要维护红黑树或者符号表，而且还要做哈希函数的运算。所以数组更加简单直接有效！

使用数组和set来做哈希法的局限：
数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。

三、解题思路

题号	思路	相关主题	难度
1.?Two Sum	暴力解：O(n^2) 哈希表：map，O(n) ?map中的存储结构为 {key：数据元素，value：数组元素对应的下表} 在遍历数组的时候，只需要向map去查询是否有和目前遍历元素匹配的数值，如果有，就找到的匹配对，如果没有，就把目前遍历的元素放进map中，因为map存放的就是我们访问过的元素。	数组 HashMap	easy
454.?4Sum II	本题适合使用哈希表 a+b c+d, 遍历a+b, 遍历0 -（c+d）是否在map里，count计数 map的key存放的是i+j之和，value存放的是和出现的次数，后面0-（i+j）直接取出	数组 HashMap	medium
383.?Ransom Note	关键词：只有小写字母方法一：创建两个map，分别统计两个String的char及出现次数，最好进行是否含有或个数的判断方法二：创建一个map，统计ransomnote，在遍历magazine的时候将map里包含的char的个数减去，直到为0删去（这个操作要在map.containsKey(c)的时候进行，否则会报空指针错误）。最后判断map是否为空。方法三：用一个长度为26的数组还记录magazine里字母出现的次数。其实在本题的情况下，使用map的空间消耗要比数组大一些的，因为map要维护红黑树或者哈希表，而且还要做哈希函数，是费时的！数据量大的话就能体现出来差别了。所以数组更加简单直接有效！	String HashMap	easy
15.?3Sum	Arrays.sort(nums); 不建议使用哈希法，因为需要去重说道去重，其实主要考虑三个数的去重。 a, b ,c, 对应的就是 nums[i]，nums[left]，nums[right]。a 如果重复了怎么办，a是nums里遍历的元素，那么应该直接跳过去。判断 nums[i] 与 nums[i-1] 是否相同。b与c的去重，在最后找到了再去重即可，不用提前去重。主逻辑：sum>0, right--; sum<0, left++; sum==0,说明找到了答案。剪枝：if (nums[i] > 0) { ? ? ? ? ? ? ? ? return result; ? ? ? ? ? ? } 这个剪枝部分有点难想到，没想到算了，不影响解题。技巧：将数组转化成list，result.add(Arrays.asList(nums[i], nums[left], nums[right]));	数组双指针	medium
18.?4Sum	Arrays.sort(nums); 遍历逻辑：for(int i=0; i<nums.length-3; i++) for(int j=i+1; j<nums.length-2; j++) while(left<right) 主逻辑还是判断sum跟target的大小去重：if(i>0 && nums[i-1]==nums[i]) continue; if(j>i+1 && nums[j-1]==nums[j]) continue; while(k<l && nums[k-1]==nums[k]) k++; while(k<l && nums[l]==nums[l+1]) l--;	数组双指针	medium

四、总结

? ? ? ? 1、数组也可以用来保存、记录信息，例如LeetCode第383题、第395题。

? ? ? ? 2、3 sum, 4 sum题型有模板：

? ? ? ? ? ? ? ? 1）Arrays.sort(nums);

? ? ? ? ? ? ? ? 2）去重：if (i > 0 && nums[i] == nums[i - 1]) {continue;}

????????????????????????while (right > left && nums[right] == nums[right - 1]) right--;
? ? ? ? ? ? ? ? ? ? ? ? ?while (right > left && nums[left] == nums[left + 1]) left++;?

? ? ? ? ? ? ? ? 3）left, right->while (left < right){}

? ? ? ? ? ? ? ? 4）主逻辑：sum < target, sum > target, sum == target

? ? ? ? ? ? ? ? 5）Arrays.asList();

???????????????????????result.add(Arrays.asList(nums[i], nums[left], nums[right]));

? ? ? ? 3、4 sum II：map对两组数组的统计（个数），if(map.containsKey(0-temp))