当前位置：首页 > news >正文

【LeetCode】力扣刷题热题100道（16-20题）附源码容器子数组数组连续序列三数之和（C++）

news 来源：原创 2025/5/15 1:51:59

1.盛最多水的容器

2.和为K的子数组

3.最大子数组和

4.最长连续序列

5.三数之和

1.盛最多水的容器

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

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

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

说明：你不能倾斜容器。

如下为代码：

class Solution {
public:int maxArea(vector<int>& height) {int left = 0, right = height.size() - 1;int max_area = 0;while (left < right) {// 计算当前容器的水量int current_area = min(height[left], height[right]) * (right - left);// 更新最大水量max_area = max(max_area, current_area);// 移动指针if (height[left] < height[right]) {left++;} else {right--;}}return max_area;}
};

初始化两个指针，left 指向数组的开头，right 指向数组的末尾。
每次计算当前指针所指的两条线所能容纳的水量，并更新最大水量。
根据容器的高度，移动指针：如果 height[left] 小于 height[right]，则移动 left 指针，否则移动 right 指针。这样可以尝试更大的水量，因为较短的线影响水量的大小，移动较短的线可能会找到更大的容器。
最终返回最大水量。

2.和为K的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。

class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int, int> sumCount; sumCount[0] = 1;  int currentSum = 0; int result = 0; for (int num : nums) {currentSum += num; if (sumCount.find(currentSum - k) != sumCount.end()) {result += sumCount[currentSum - k];}sumCount[currentSum]++;}return result;}
};

sumCount 哈希表：

sumCount 的键是前缀和，值是该前缀和出现的次数。初始时，我们将 sumCount[0] 设置为 1，表示前缀和为 0 的子数组出现过一次。
currentSum：

currentSum 用来记录当前遍历位置的前缀和。每遍历一个元素，我们就将当前元素加到 currentSum 上。
result：

result 用来存储符合条件的子数组的个数。
查找条件：

在每次更新 currentSum 时，判断 sumCount[currentSum - k] 是否存在。如果存在，说明有子数组和为 k，我们就将 sumCount[currentSum - k] 的值加到 result 中。
更新哈希表：每次遍历完一个元素后，更新哈希表中的 currentSum 出现次数。

3.最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组
是数组中的一个连续部分。

class Solution {
public:int maxSubArray(vector<int>& nums) {int currentSum = nums[0]; int maxSum = nums[0];  for (int i = 1; i < nums.size(); i++) {currentSum = max(nums[i], currentSum + nums[i]);maxSum = max(maxSum, currentSum);}return maxSum;}
};

最终返回 maxSum = 6。

currentSum：

currentSum 表示当前以 nums[i] 结尾的子数组的和。我们会选择当前的 nums[i] 单独作为一个新的子数组，或者将其加入到 currentSum 中，取决于哪种选择能使和更大。
maxSum：

maxSum 是记录到当前为止的最大子数组和。我们在每一步更新 currentSum 后，检查是否需要更新 maxSum。
动态规划的递推关系：

currentSum = max(nums[i], currentSum + nums[i])：如果 currentSum + nums[i] 更大，就继续扩大当前子数组；否则，从当前位置 i 开始新一个子数组。
maxSum = max(maxSum, currentSum)：更新全局的最大子数组和。
假设 nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]：初始化时，currentSum = -2 和 maxSum = -2。
第2个元素：currentSum = max(1, -2 + 1) = 1，maxSum = max(-2, 1) = 1。
第3个元素：currentSum = max(-3, 1 + (-3)) = -2，maxSum = max(1, -2) = 1。
第4个元素：currentSum = max(4, -2 + 4) = 4，maxSum = max(1, 4) = 4。
第5个元素：currentSum = max(-1, 4 + (-1)) = 3，maxSum = max(4, 3) = 4。
第6个元素：currentSum = max(2, 3 + 2) = 5，maxSum = max(4, 5) = 5。
第7个元素：currentSum = max(1, 5 + 1) = 6，maxSum = max(5, 6) = 6。
第8个元素：currentSum = max(-5, 6 + (-5)) = 1，maxSum = max(6, 1) = 6。
第9个元素：currentSum = max(4, 1 + 4) = 5，maxSum = max(6, 5) = 6。

4.最长连续序列

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

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

class Solution {
public:int longestConsecutive(vector<int>& nums) {unordered_set<int> numSet(nums.begin(), nums.end()); int longestStreak = 0;for (int num : numSet) {if (numSet.find(num - 1) == numSet.end()) {int currentNum = num;int currentStreak = 1;while (numSet.find(currentNum + 1) != numSet.end()) {currentNum++;currentStreak++;}longestStreak = max(longestStreak, currentStreak);}}return longestStreak;}
};

去重：首先将输入的数组 nums 转换为哈希集合 numSet，这样就去除了重复的元素，并且能够在常数时间内检查元素是否存在。
查找最长连续序列：
对于每一个数字 num，我们检查 num - 1 是否存在于集合中。如果不存在，说明 num 是某个连续序列的起始元素。
然后从 num 开始，逐个检查 num + 1, num + 2, ... 是否存在于集合中，直到遇到不存在的元素。
更新最长序列长度：在每次查找完一个序列后，更新 longestStreak 以记录目前为止找到的最长连续序列的长度。

5.三数之和

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

如下代码：

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> result;sort(nums.begin(), nums.end()); // 排序数组for (int i = 0; i < nums.size(); ++i) {if (i > 0 && nums[i] == nums[i - 1]) continue; // 跳过重复的固定元素int left = i + 1, right = nums.size() - 1;while (left < right) {int sum = nums[i] + nums[left] + nums[right];if (sum == 0) {result.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;} else if (sum < 0) {++left; // 和小于零，左指针右移增大和} else {--right; // 和大于零，右指针左移减小和}}}return result;}
};

排序数组：

通过 sort(nums.begin(), nums.end())，便于使用双指针方法。

跳过重复元素：

在外层循环中，如果当前 nums[i] 等于前一个值，则跳过。

在双指针部分，跳过连续相同的值以避免重复结果。

双指针查找：

左右指针收缩查找满足条件的组合。根据当前和的值决定移动左指针还是右指针。

1.盛最多水的容器

2.和为K的子数组

3.最大子数组和

4.最长连续序列

5.三数之和

相关文章：