167. 两数之和 II - 输入有序数组
题目
给你一个下标从1开始的整数数组numbers，该数组已按**非递减顺序排列。
请你从数组中找出满足相加之和等于目标数target的两个数。令这两个数分别是numbers[index_(1)]和numbers[index_(2)]，其中1 <= index_(1) < index_(2) <= numbers.length。
以长度为 2 的整数数组[index_(1), index_(2)]的形式返回这两个整数的下标index_(1)和index_(2)。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
你所设计的解决方案必须只使用常数级的额外空间。
示例 1：
输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。示例 2：
输入：numbers = [2,3,4], target = 6 输出：[1,3] 解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。示例 3：
输入：numbers = [-1,0], target = -1 输出：[1,2] 解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。提示：
2 <= numbers.length <= 3 * 10^(4)-1000 <= numbers[i] <= 1000numbers按非递减顺序排列-1000 <= target <= 1000仅存在一个有效答案
当前编辑器代码
class Solution { public: vector<int> twoSum(vector<int>& numbers, int target) { int l=0,r=numbers.size()-1; while(l<r){ int s=numbers[l]+numbers[r]; if(s>target){ r--; } else if(s<target){ l++; } else break; } return {l+1,r+1}; } };15. 三数之和
题目
给你一个整数数组nums，判断是否存在三元组[nums[i], nums[j], nums[k]]满足i != j、i != k且j != k，同时还满足nums[i] + nums[j] + nums[k] == 0。请你返回所有和为0且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。示例 2：
输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。示例 3：
输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。提示：
3 <= nums.length <= 3000-10^(5) <= nums[i] <= 10^(5)
当前编辑器代码
/* 时间复杂度o(n^2) 空间o(n) 一定要有序的数，进行sort 参考两数之和167 我们可以遍历i，就可以得到n[j]+n[k]=-n[i]=常数 不重复三元组，故要判断i+1与i是否相同 判断优化： n[i]与前两个数相加>0可以跳过 n[i]与后两个数相加<0可以跳过 */ class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { int n=nums.size()-1; sort(nums.begin(),nums.end()); vector<vector<int>> ans; for(int k=0;k<=n-2;k++){ int target=nums[k]; int l=k+1,r=n; if(k>0&&nums[k]==nums[k-1])continue; if(target+nums[k+1]+nums[k+2]>0)break; if(target+nums[n]+nums[n-1]<0)continue; while(l<r){ if(nums[l]+nums[r]+target>0){ r--; } else if (nums[l]+nums[r]+target<0){ l++; } else { ans.push_back({nums[l],nums[r],target}); l++,r--; while(l<r&&nums[l]==nums[l-1])l++; while(l<r&&nums[r]==nums[r+1])r--; } } } return ans; } };11. 盛最多水的容器
题目
给定一个长度为n的整数数组height。有n条垂线，第i条线的两个端点是(i, 0)和(i, height[i])。
找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
示例 1：
输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。示例 2：
输入：height = [1,1] 输出：1提示：
n == height.length2 <= n <= 10^(5)0 <= height[i] <= 10^(4)
当前编辑器代码
/*相向双指针 随便两条线，无论往里面怎么移动，都是由Min（hl,hr）决定的，而宽度变短，故面积一定变小 所以移动短的那条线,i++/j-- */ class Solution { public: int maxArea(vector<int>& height) { int l=0,r=height.size()-1; int area=0; int s=0; while(l<r){ s=(r-l)*min(height[l],height[r]); area=max(area,s); if(height[l]>height[r])r--; else l++; } return area; } };42. 接雨水
题目
给定n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。示例 2：
输入：height = [4,2,0,3,2,5] 输出：9提示：
n == height.length1 <= n <= 2 * 10^(4)0 <= height[i] <= 10^(5)
当前编辑器代码
/* 前后缀、相向双指针优化了空间o(1) 时间o(n) 柱子能接的水取决于左边的木板和右边的木板->前缀、后缀 即min(pre[i],suf[i])-h Sum()就是最终结果 双指针l,r 若是后缀r已经大于前缀l了，该柱子min就是前缀l，优化了空间 */ class Solution { public: int trap(vector<int>& h) { int n=h.size(); int l=0,r=n-1; int ans=0; int lm=0,rm=0; while(l<r){ lm=max(lm,h[l]); rm=max(rm,h[r]); if(h[l]<h[r]){ ans+=lm-h[l]; l++; } else{ ans+=rm-h[r]; r--; } } return ans; } };
空间解法)
