力扣面试题解析：哈希表与双指针算法

哈希表

哈希表（散列表）是一种通过键值对映射来高效存储和查找数据的数据结构。其核心思想是使用一个哈希函数，将键（Key）转换为数组索引，从而直接定位对应的值，实现 O(1) 时间复杂度的增删改查。

特性：高效读写、基于哈希函数映射、处理哈希冲突（链地址法、开放寻址法）、空间换时间、无序性

1. 两数之和

给定整数数组 nums 和目标值 target，找出和为目标值的两个整数并返回下标。

• 使用字典存储值和对应的索引

class Solution(object):
    def twoSum(self, nums, target):
        num_map = {}
        for index, num in enumerate(nums):
            x = target - num
            if x in num_map:
                return [num_map[x], index]
            num_map[num] = index

2. 字母异位词分组

将字符串数组中的字母异位词组合在一起。

• 生成特征键：为相似元素找唯一标识
• 方法：排序法、计数法
• 排序法：key = ''.join(sorted(x))

class Solution(object):
    def groupAnagrams(self, strs):
        list1 = {}
        for x in strs:
            key = ''.join(sorted(x))
            if key not in list1:
                list1[key] = []
            list1[key].append(x)
        return list(list1.values())

3. 最长连续序列

在未排序整数数组中找出数字连续的最长序列长度。

1. 转集合去重
2. 遍历集合，若 num-1 不存在则 num 为起点
3. 从起点向后查找连续数字
4. 维护最大长度

class Solution(object):
    def longestConsecutive(self, nums):
        num_set = set(nums)
        max_length = 0
        for num in num_set:
            if num - 1 not in num_set:
                current_num = num
                current_length = 1
                while current_num + 1 in num_set:
                    current_num += 1
                    current_length += 1
                if current_length > max_length:
                    max_length = current_length
        return max_length

双指针

在数组或链表上使用两个指针协同移动，减少重复计算。指针可同向或相向移动。

类型：快慢指针（判断环、中间节点）、左右指针（两数之和、反转数组）、滑动窗口（最长无重复子串） 特性：时间效率高、空间复杂度低、适合有序数组/区间类问题

1. 移动零

将所有 0 移动到末尾，保持非零元素相对顺序。

• 慢指针：记录非零元素放置位置
• 快指针：遍历寻找非零元素
• 交换并右移

class Solution(object):
    def moveZeroes(self, nums):
        slow = 0
        for fast in range(len(nums)):
            if nums[fast] != 0:
                nums[slow] = nums[fast]
                slow += 1
        for x in range(slow, len(nums)):
            nums[x] = 0
        return nums

2. 盛水最多的容器

给定高度数组 height，求两条线与 x 轴构成的最大面积。

• 初始指针：左头右尾
• 面积由最短边决定
• 移动较短边的指针

class Solution(object):
    def maxArea(self, height):
        left, right = 0, len(height) - 1
        max_area = 0
        while left < right:
            current_area = min(height[left], height[right]) * (right - left)
            if current_area > max_area:
                max_area = current_area
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return max_area

3. 三数之和

返回所有和为 0 且不重复的三元组。

• 排序预处理
• 固定第一个数，双指针找另外两个
• 去重处理

class Solution(object):
    def threeSum(self, nums):
        nums.sort()
        result = []
        n = len(nums)
        for i in range(n):
            if nums[i] > 0:
                break
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            left, right = i + 1, n - 1
            target = -nums[i]
            while left < right:
                current_num = nums[left] + nums[right]
                if current_num == target:
                    result.append([nums[i], nums[left], nums[right]])
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1
                elif current_num < target:
                    left += 1
                else:
                    right -= 1
        return result