哈希双指针
文章目录
- 一、哈希
- 1.1两数之和
- 1.2字母异位词分组
- 1.3最长子序列
- 二、双指针
- 2.1[移动零](https://leetcode.cn/problems/move-zeroes/description/?envType=study-plan-v2&envId=top-100-liked)
- 2.2[盛最多水的容器](https://leetcode.cn/problems/container-with-most-water/description/?envType=study-plan-v2&envId=top-100-liked)
- 2.3[三数之和](https://leetcode.cn/problems/3sum/description/?envType=study-plan-v2&envId=top-100-liked)
- 2.4[接雨水](https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-100-liked)
一、哈希
1.1两数之和
力扣链接：两数之和
方法1：暴力枚举
直接两个for循环，从头到尾循环一遍，碰见相等就直接从循环跳出，但是效率很低，时间复杂度高
方法2：哈希
先实例化一个哈希表，unordered_map，然后开始for循环，for循环不需要判断条件，sum - 当前的数如果在哈希表中找不到，那么我们就直接把当前的数插入到哈希表中，以此类推。
哈希解法图解
1.2字母异位词分组
题目链接
方法1：暴力枚举
两个for循环，每取出一个字符串就sort一下，看是不是与其匹配的字符串，是的就直接emplace_back到vector<vector<string>>中，效率低，时间复杂度高
方法2：哈希（图解）
1.3最长子序列
题目链接
方法1：排序+循环
方法2：哈希
二、双指针
2.1移动零
2.2盛最多水的容器
2.3三数之和
用双指针维护区间长度，先排序再找目标值，然后利用单调性来维护区间长度
2.4接雨水
