📝前言說明：

• 本專欄主要記錄本人的基礎算法學習以及LeetCode刷題記錄，按專題劃分
• 每題主要記錄：（1）本人解法 + 本人屎山代碼；（2）優質解法 + 優質代碼；（3）精益求精，更好的解法和獨特的思想（如果有的話）
• 文章中的理解僅為個人理解。如有錯誤，感謝糾錯

🎬個人簡介：努力學習ing
📋本專欄：C++刷題專欄
📋其他專欄：C語言入門基礎，python入門基礎，C++學習筆記，Linux
🎀CSDN主頁 愚潤澤

---

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;}
};

時間復雜度：O(n)
空間復雜度：O(1)

---

優質解：

我還是把我的思路畫出來吧。

理解1
接水量一定由短邊決定，如圖：

理解2
假如，左側的邊短于右側的邊，則往里面走，裝水量一定由左側的最長邊決定，如圖：

---

🌈我的分享也就到此結束啦🌈
要是我的分享也能對你的學習起到幫助，那簡直是太酷啦！
若有不足，還請大家多多指正，我們一起學習交流！
📢公主，王子：點贊👍→收藏?→關注🔍
感謝大家的觀看和支持！祝大家都能得償所愿，天天開心！！！