26. 删除有序数组中的重复项
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
判题标准:
系统会用下面的代码来测试你的题解:
int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案
int k = removeDuplicates(nums); // 调用
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
如果所有断言都通过，那么您的题解将被 通过。
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
提示：
0 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按 升序 排列
思考：这道题需要返回数组的新长度 k，且断言处需要判定 数组前k个值不可以有重复项
题解：
public int removeDuplicates(int[] nums) {
// 本题需要返回的数组的新长度 k，且断言处需要判定 数组前k个值不可以有重复项
// 拿到数组不要先着急遍历删除，对于数组可以考虑快慢（双）指针是否可以使用
int fast = 1, slow = 1; // 定义两个指针
while (fast < nums.length) { // 快指针范围
if (nums[fast] != nums[fast - 1]) { // 快指针比较是否和上一个位置的数是不同的
nums[slow] = nums[fast]; // 交换数
++slow; // 慢指针走一步
}
++fast; // 每次循环快指针负责遍历数组
}
return slow;
} 15. 三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = []
输出：[]
示例 3：
输入：nums = [0]
输出：[]
思考：这道题可以用暴力解法做，三层循环，找到所有符合的元素，时间复杂度是O(n^3)；
如果用双指针，我们需要整个数组排序，从第一个数遍历，后面的只需要找到两个数是这个数的负数（转化为力扣第一题两数之和的问题）
题解：
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums); // 排序
List<List<Integer>> ans = new ArrayList<List<Integer>>(); // 定义返回的数据结构
// 遍历 a
for (int first = 0; first < nums.length; ++first) {
// 需要和上一次枚举的数不相同(为了去重)
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
// 下面转化为两数之和问题
int third = nums.length - 1; // c 对应的指针初始指向数组的最右端
int target = -nums[first]; // 目标值是a的负数
// 枚举 b
for (int second = first + 1; second < nums.length; ++second) {
// 需要和上一次枚举的数不相同(为了去重)
if (second > first + 1 && nums[second] == nums[second - 1]) {
continue;
}
// 需要保证 b 的指针在 c 的指针的左侧
while (second < third && nums[second] + nums[third] > target) {
--third;
}
// 如果指针重合，随着 b 后续的增加
// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
if (second == third) {
break;
}
// 将符合的三个元素加入到目标集合中
if (nums[second] + nums[third] == target) {
List<Integer> list = new ArrayList<Integer>();
list.add(nums[first]);
list.add(nums[second]);
list.add(nums[third]);
ans.add(list);
}
}
}
return ans;
} 42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
【2022/03/15】力扣押题推荐(删除有序数组重复项、三数之和、接雨水) 示例 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.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
思考：这道题可以使用，暴力法：直接按问题描述进行。对于数组中的每个元素，我们找出下雨后水能达到的最高位置，等于两边最大高度的较小值减去当前高度的值。
数学法：两边面积相减，在暴力方法中，我们仅仅为了找到最大值每次都要向左和向右扫描一次。但是我们可以提前存储这个值。因此，可以通过动态编程解决。
public int trap(int[] height) {
int ans = 0; // 接雨水的面积
int left = 0, right = height.length - 1; // 左右指针
int leftMax = 0, rightMax = 0;
while (left < right) { // 左右指针向中间夹逼
leftMax = Math.max(leftMax, height[left]); // 保留左指针，当前情况（本次循环），最高的位置
rightMax = Math.max(rightMax, height[right]); // 保留右指针，当前情况（本次循环），最高的位置
// 如果 height[left]<height[right]，则必有 leftMax<rightMax
if (height[left] < height[right]) {
ans += leftMax - height[left]; // 下标left处能接的雨水量等于leftMax−height[left]
++left; // 将下标 left 处能接的雨水量加到能接的雨水总量，然后将left 加 1
} else { // 判断如果左边比右边大，
ans += rightMax - height[right];
--right;
}
}
return ans;
}