力扣里面关于哈希的题目有哪些

### LeetCode 上的 C++ 编程问题推荐 LeetCode 是学习算法和数据结构的一个重要平台，它提供了大量的编程挑战，其中许多都可以通过 C++ 来解决。以下是几个适合初学者到中级水平的经典题目列表： #### 数据结构基础 1. **两数之和 (Two Sum)** 这是一个经典的入门级问题，可以通过哈希表来优化时间复杂度[^2]。 ```cpp class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> map; for(int i=0;i<nums.size();i++) { if(map.find(target - nums[i]) != map.end()) { return {map[target - nums[i]], i}; } map[nums[i]] = i; } return {}; } }; ``` 2. **有效的括号 (Valid Parentheses)** 使用栈的数据结构可以轻松验证给定字符串中的括号是否匹配[^3]。 #### 动态规划 1. **爬楼梯 (Climbing Stairs)** 此问题是动态规划的基础应用之一，类似于斐波那契序列计算[^4]。 2. **最大子数组和 (Maximum Subarray)** 应用 Kadane's Algorithm 可以在线性时间内找到具有最大和的连续子数组[^5]。 #### 字符串处理 1. **反转字符串单词 III (Reverse Words in a String III)** 需要对字符串进行分割并逐个翻转每个单词[^6]。 2. **最长公共前缀 (Longest Common Prefix)** 找出多个输入字符串之间的共同起始部分[^7]。 #### 图与树 1. **二叉树的最大深度 (Maximum Depth of Binary Tree)** 利用递归来遍历整个二叉树，并记录其最大深度[^8]。 ```cpp /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int maxDepth(TreeNode* root) { if(root == nullptr){ return 0; }else{ int ldepth = maxDepth(root->left); int rdepth = maxDepth(root->right); return std::max(ldepth,rdepth)+1; } } }; ``` 2. **岛屿数量 (Number of Islands)** 经典图搜索问题，通常采用广度优先搜索(BFS)或者深度优先搜索(DFS)[^9]。 ---

### 关于前缀和算法的相关 LeetCode 练习题 前缀和是一种常见的优化技巧，用于快速计算数组中子区间的和。以下是几道经典的基于前缀和算法的 LeetCode 题目： #### 1. **Range Sum Query - Immutable** 这是一道基础的前缀和题目，目标是在给定数组的情况下多次查询某个区间 `[i, j]` 的和。通过构建前缀和数组 `prefixSum` 可以将每次查询的时间复杂度降低到 O(1)[^4]。 ```cpp class NumArray { public: vector<int> prefix; NumArray(vector<int>& nums) { int n = nums.size(); prefix.resize(n + 1); for (int i = 0; i < n; ++i) { prefix[i + 1] = prefix[i] + nums[i]; } } int sumRange(int left, int right) { return prefix[right + 1] - prefix[left]; } }; ``` #### 2. **Maximum Subarray** 虽然该问题通常使用 Kadane's Algorithm 解决，但它也可以通过前缀和的方式求解最大子数组和[^3]。核心思路是记录当前最小的前缀和以及当前位置的最大差值。 #### 3. **Subarray Sum Equals K** 此问题是前缀和的一个典型扩展版本，要求找到和等于特定值 `k` 的连续子数组的数量。可以通过哈希表存储之前遇到过的前缀和及其频率来加速查找过程[^5]。 ```python def subarraySum(nums, k): count = 0 sums = 0 d = {} d[0] = 1 for num in nums: sums += num if sums - k in d: count += d[sums - k] if sums not in d: d[sums] = 0 d[sums] += 1 return count ``` #### 4. **Product of Array Except Self** 尽管这不是典型的前缀和问题，但其解决方案涉及类似的累积操作。分别从前向后和从后向前计算两个方向上的乘积作为辅助数组的一部分[^6]。 --- ###