LeetCode 热题100专题解析：哈希与双指针
本文将重点解析 LeetCode 热题100 中关于哈希和双指针的题目，帮助读者更好地理解和掌握这两种算法思想。
哈希表专题
- 两数之和
**题目描述：**给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
**解题思路：**这是一道典型的哈希表应用题目。我们可以遍历数组，对于每个元素，计算目标值与当前元素的差值，然后检查这个差值是否存在于已经遍历过的元素中。如果存在，那么我们就找到了一对和为目标值的数。
- 字母异位词分组
**题目描述：**给定一个字符串数组，将字母异位词的字符串分组在一起。
**解题思路：**这个问题可以通过哈希表来解决。我们可以遍历每个字符串，计算它的字母频率（例如，‘a’ 出现的次数、‘b’ 出现的次数等），然后将这个频率作为键值存储在哈希表中。接着，对于每个新的字符串，我们检查它的字母频率是否已经存在于哈希表中，如果存在，就将它添加到对应的列表中。
双指针专题
- 移动零
**题目描述：**给定一个数组，将所有 0 移动到数组的末尾，保持非零元素的相对顺序。
**解题思路：**这是一个经典的双指针问题。我们可以使用两个指针，一个指针遍历数组，另一个指针指向当前非零元素的位置。当我们遇到非零元素时，就将它与指针指向的位置交换，然后移动指针。
- 盛最多水的容器
**题目描述：**给定一个由非负整数表示的数组，用来表示容器的宽度和高度。计算由这些容器组成的堤坝能盛多少水。
**解题思路：**这个问题可以通过双指针来解决。我们维护两个指针，一个在数组的开始，另一个在数组的末尾。这两个指针代表堤坝的两端。我们计算由这两个指针形成的堤坝能盛多少水，然后移动能形成更大堤坝的一端的指针。
- 三数之和
**题目描述：**给定一个包含 n 个数字的数组，找出所有三元组，使得这些数的和为 0。
**解题思路：**虽然这个问题看起来需要三重循环，但实际上可以通过双指针技术来优化。首先对数组进行排序，然后遍历数组，对于每个元素，我们使用两个指针分别指向当前元素的左右两侧，尝试找到和为 0 的三元组。
- 接雨水
**题目描述：**给定 n 个非负整数，用以表示房屋的高度。如果雨水从上到下落下来，计算雨水能接多少。
**解题思路：**这个问题可以通过双指针和动态规划的结合来解决。我们维护一个数组来保存每个位置左边和右边的最高条形块。然后遍历原数组，计算每个位置能接的雨水量，即当前位置的房屋高度与左右两边最高条形块中的较小者之差。