LeetCode 热题 100 精讲 | 数组篇：两数之和 · 盛最多水的容器 · 三数之和
一、1. 两数之和
🔗 题目链接
📝 题目描述
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那 两个 整数，并返回它们的数组下标。每种输入只会对应一个答案，且同一个元素不能重复使用。
示例：
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9，返回 [0, 1]。
🧠 思路分析
暴力解法是用两层循环遍历所有数对，复杂度 O(n²)，面对大数据量时效率太低。哈希表解法可以在 O(n) 时间内解决问题。具体做法是：遍历数组时，对于当前元素 nums[i]，计算 target - nums[i]，然后在哈希表中查找这个差值是否存在。如果存在，说明前面已经出现了对应的数字，直接返回两个下标。如果不存在，就把当前数字和它的下标存入哈希表，供后面元素匹配使用。这样每走一步都在用 O(1) 的时间查询哈希表，整体只需遍历一次数组。另外注意哈希表存储的是已经遍历过的元素，所以不会出现同一个元素被使用两次的情况。
💻 代码实现（C++）
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hash;
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
if (hash.find(complement) != hash.end()) {
return {hash[complement], i};
}
hash[nums[i]] = i;
}
return {};
}
};📚 相关学习资源
（若链接失效或侵权，请联系删除）
⏱ 复杂度分析
-
时间复杂度：O(n)。一次遍历，每次哈希表操作 O(1)。
-
空间复杂度：O(n)。哈希表最多存储 n 个元素。
二、53. 最大子数组和
🔗 题目链接
📝 题目描述
给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6。
🧠 思路分析
这道题的核心是著名的 Kadane 算法，本质是动态规划。定义 dp[i] 表示以 nums[i] 结尾的连续子数组的最大和，那么状态转移方程就是 dp[i] = max(nums[i], dp[i-1] + nums[i])。通俗地说，当遍历到第 i 个元素时，要么把它接在之前的子数组后面继续累加，要么就以它自己为起点新开一个子数组，两者取最大值。最终答案就是所有 dp[i] 中的最大值。注意这里可以用一个变量滚动记录 dp[i-1]，从而把空间复杂度降到 O(1)，也就是只用一个 cur 表示以当前元素结尾的最大和，再用一个 res 记录全局最大值即可。
💻 代码实现（C++）
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int cur = nums[0];
int res = nums[0];
for (int i = 1; i < nums.size(); i++) {
cur = max(nums[i], cur + nums[i]);
res = max(res, cur);
}
return res;
}
};📚 相关学习资源
（若链接失效或侵权，请联系删除）
⏱ 复杂度分析
-
时间复杂度：O(n)。一次遍历即可完成。
-
空间复杂度：O(1)。只用常数个变量。
三、15. 三数之和
🔗 题目链接
📝 题目描述
给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。返回所有和为 0 且不重复的三元组。
示例：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
🧠 思路分析
暴力解法需要三层循环，复杂度 O(n³)，显然不可行。先对数组排序，这样重复元素就会紧挨在一起，便于去重。排序后，固定第一个数 nums[i]，然后在剩下的区间 [i+1, n-1] 中用双指针寻找两个数，使得它们的和等于 -nums[i]。双指针一头一尾向中间移动：若当前和小于目标值，左指针右移；若当前和大于目标值，右指针左移；若相等，记录答案，然后左右指针同时跳过重复元素，继续寻找下一组。外层循环遍历 i 时也要跳过重复的 nums[i]，否则答案里会出现重复的三元组。这个排序加双指针的方案能把时间复杂度降到 O(n²)，排序 O(n log n) 加上遍历固定和双指针移动 O(n²)。
💻 代码实现（C++）
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
int n = nums.size();
for (int i = 0; i < n - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1, right = n - 1;
int target = -nums[i];
while (left < right) {
int sum = nums[left] + nums[right];
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
res.push_back({nums[i], nums[left], nums[right]});
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
}
}
}
return res;
}
};📚 相关学习资源
（若链接失效或侵权，请联系删除）
⏱ 复杂度分析
-
时间复杂度：O(n²)。排序 O(n log n) 可以忽略，外层循环 O(n) 内层双指针 O(n)。
-
空间复杂度：O(log n) ~ O(n)，取决于排序算法的栈空间。
四、11. 盛最多水的容器
🔗 题目链接
📝 题目描述
给定一个长度为 n 的整数数组 height，有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水（即面积最大）。不能倾斜容器。
示例：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组，在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
🧠 思路分析
暴力枚举所有左右边界对，时间复杂度 O(n²)。双指针法可以做到 O(n)：用两个指针分别指向数组的左右两端，计算当前容器面积，然后移动高度较小的那个指针。为什么要移动高度较小的？因为容器的面积取决于宽度和较小的高度。如果移动较高的指针，宽度在减小，高度不会超过当前较小值，面积只会变得更小，没有任何机会。而移动较矮的指针，虽然宽度也在减小，但有机会遇到更高的线，让高度变大，从而有可能获得更大的面积。按照这个规则不断向内移动指针，直到两指针相遇，记录过程中出现的最大面积即可。
💻 代码实现（C++）
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0, right = height.size() - 1;
int maxArea = 0;
while (left < right) {
int h = min(height[left], height[right]);
int w = right - left;
maxArea = max(maxArea, h * w);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}
};📚 相关学习资源
（若链接失效或侵权，请联系删除）
⏱ 复杂度分析
-
时间复杂度：O(n)。左右指针各移动一次，每个元素只被访问一次。
-
空间复杂度：O(1)。只用两个指针和几个变量。
结语
数组类题目在面试中几乎必考，而这四道题恰好覆盖了最常用的四种解题套路：哈希表（两数之和）、动态规划/贪心（最大子数组和）、排序+双指针（三数之和）、对撞双指针（盛最多水的容器）。把这四种思想刻进脑子里，遇到大多数数组题都不会慌。
刷题建议：先自己动手写一遍暴力解，再对比最优解的优化点，最后把代码默写三遍。别只看不写，面试时手撕代码拼的是肌肉记忆。
如果本文对你有帮助，欢迎点赞、收藏、转发，你的支持是我持续创作的动力 ❤️
免责声明：本文部分解题思路参考了力扣官方题解及社区优秀文章，相关视频链接均来自公开网络。若存在侵权问题，请联系删除。
更多推荐
28
0- 0
已为社区贡献1条内容
所有评论(0)