目录
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] 等于前一个值，则跳过。
在双指针部分，跳过连续相同的值以避免重复结果。
双指针查找：
左右指针收缩查找满足条件的组合。根据当前和的值决定移动左指针还是右指针。
