leetcode hot100：三、解题思路大全：哈希（两数之和、字母异位词分组、最长连续序列）、双指针（移动零、盛最多水的容器、三数之和、接雨水）

哈希

两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

思路

不多说，经典题。哈希表存储已经访问过的元素和对应下标，对每次遍历的元素num都去寻找target-num是否在哈希表中，在的话就取出并返回答案，否则的话存入哈希表。

字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

思路

同样也是对每次遍历到的字符串存入哈希表，键为升序字典序的该字符串，值为该字符串及其异位词。

最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

思路

用哈希表+集合优化。
要实现时间复杂度为 O(n) 的算法，关键在于利用哈希表（或集合）快速判断元素的前驱和后继是否存在，避免重复遍历已处理的元素。核心思路如下：

• 将数组元素存入集合：利用集合（Python 中为 set）实现O(1)时间的存在性查询。
• 仅处理序列起点：对于每个元素 num，若 num-1 不存在于集合中，则说明 num 是某个连续序列的起点。从该起点开始，不断尝试扩展序列长度（判断 num+1, num+2, … 是否存在），记录最长序列长度。

双指针

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

思路

经典题，维护left和right指针。left指针指向非零元素的右边界，right指针向后遍历。

盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

思路

相当于最大水量的长和宽都不固定，所以我们用双指针从两边收缩，这样保障长是从最长长度开始收缩的，然后去寻找当前长度下的最高高度。也就是寻找当前高度下的离他最远的高度≥它的柱子。
那么双指针从两边收缩，每次收缩是移动左指针还是右指针呢？
答案是，我们只需要移动高度较小的那边。因为高度较小的那边限制了面积，只有移动他才有可能出现面积更大的情况。

三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

思路

同样经典老朋友了，将数组去重排序后，最外层循环寻找的是第一个数，left指针寻找第二个数，right指针寻找第三个数。

接雨水

思路

典中典。不多说，这道题我不喜欢用双指针，喜欢用leftMax和rightMax。