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

【专题刷题】双指针（四）：最接近的三数之和，接雨水

news 2025/5/6 3:37:56

📝前言说明：

本专栏主要记录本人的基础算法学习以及LeetCode刷题记录，按专题划分
每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）
文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页愚润泽

视频

16. 最接近的三数之和
- 个人解
- 优质解：
42.接雨水
- 个人解
- 优质解：

16. 最接近的三数之和

在这里插入图片描述

个人解

思路：和三数之和差不多，这里是最接近的话，只需要使用一个min_diff来记录差值，ans来记录答案就可以了。只是这里的双指针的移动有点区别，每次对当前组合判断完是否需要替换ans就可以直接移动了
用时：16:30
屎山代码（通过）：

class Solution {
public:int threeSumClosest(vector<int>& nums, int target) {ranges::sort(nums);int ans, n = nums.size();int min_diff = INT_MAX; for(int i = 0; i < n - 2; i++){if(i && nums[i - 1] == nums[i])continue;int x = nums[i];int s = x + nums[i + 1] + nums[i + 2];if(s > target){if(s - target < min_diff){min_diff = target - s;ans = s;}break;}s = x + nums[n-2] + nums[n-1];if(s < target){if(target - s < min_diff){min_diff = target - s;ans = s;}continue;}int j = i + 1, k = n - 1;while(j < k){s = x + nums[j] + nums[k];if(s == target)return target;else if(s > target){if(s - target < min_diff){min_diff = s - target;ans = s;}k--;}else {if(target - s < min_diff){min_diff = target - s;ans = s;}j++;}}}return ans;}
};

时间复杂度：O( $n^2$ )
空间复杂度：O(1)

优质解：

无，主要借鉴别人的代码优化部分。

42.接雨水

在这里插入图片描述

个人解

思路：

装水一定是由短边决定的
我们把每一个格子都看做是一个容器
一个格子能装多少水，是由短边和自身柱子的高度决定的，即短边高 - 自身柱子高
但是这个短边不是指格子旁边的短边，是指左侧最高边和右侧最高边之间较短的那一个。
为什么是最高边？因为最高边一定能把里面的水都围住，没有水能流出去。

具体代码实现：

left指向左边的柱子，right指向右边的柱子，用left_max指向左侧的最高边，right_max指向右侧的最高边。
每次装水装的是短边的那边的格子的水。
一个格子的装水量v = min(left_max, right-max) - 该格子柱子高度。
哪边装完水哪边就移动。

用时：22:40
屎山代码（通过）：

class Solution {
public:int trap(vector<int>& height) {int left = 0, ans = 0, right = height.size() - 1, left_max = 0, right_max = 0;while(left < right){left_max = max(left_max, height[left]);right_max = max(right_max, height[right]);if(left_max < right_max){ans += left_max - height[left];left++; }else{ans += right_max - height[right];right--;}}return ans;}
};