283. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
提示:
1 <= nums.length <= 104-231 <= nums[i] <= 231 - 1
进阶：你能尽量减少完成的操作次数吗？
class Solution {
public void moveZeroes(int[] nums) {
int n = nums.length;
if (n == 0 || n == 1) {
return;
}
int j = 0;
for (int i = 0; i < n; i++) {
if (nums[i] != 0) {
nums[j++] = nums[i];
}
}
while (j < n) {
nums[j] = 0;
j++;
}
}
}从左到右遍历数组，把非0的元素移动到数组头部，用指针 j 记录偏移量，然后把剩下的元素置为0即可。
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 <= 1050 <= height[i] <= 104
class Solution {
public int maxArea(int[] height) {
int n = height.length;
int max = 0;
int i = 0, j = n - 1;
while(i < j) {
max = Math.max(max, (j - i) * Math.min(height[i], height[j]));
if (height[i] < height[j]) {
i++;
} else {
j--;
}
}
return max;
}
}定义双指针，初始分别在数组的两端，先计算最大面积，再根据条件判断移动指针，指向较小高度柱子的指针向左或向右移动直到相遇即可。
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-105 <= nums[i] <= 105
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int n = nums.length;
// 升序排序数组
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
int i = 0;
while (i < n) {
// 大于 0 已经没有意义
if (nums[i] > 0) return ans;
// 跳过重复的数
if (i >= 1 && nums[i] == nums[i - 1]) {
i++;
continue;
};
int j = i + 1;
int k = n - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
if (sum > 0) {
// 过大需要 k 左移
k--;
// 若左移之后的数还是和之前一样 继续左移
while (k > 0 && nums[k] == nums[k + 1]) {
k--;
}
} else if (sum < 0) {
// 过小需要 j 右移
j++;
// 若右移之后的数还是和之前一样 继续右移
while (j < n && nums[j] == nums[j - 1]) {
j++;
}
} else {
// sum == 0
ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[k])));
j++;
k--;
// 若左移之后的数还是和之前一样 继续左移
while (k > 0 && nums[k] == nums[k + 1]) {
k--;
}
// 若右移之后的数还是和之前一样 继续右移
while (j < n && nums[j] == nums[j - 1]) {
j++;
}
}
}
i++;
}
return ans;
}
}本题的关键是先确定一个 i 指针，然后在此基础上定义双指针 j, k，通过重复数去重达到最终答案去重的效果，因此移动之后的 while 判断必不可少，否则就需要在返回答案之前对 ans 数组去重。
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 * 1040 <= height[i] <= 105
class Solution {
public int trap(int[] height) {
int n = height.length;
int[] leftMax = new int[n];
leftMax[0] = height[0];
for (int i = 1; i < n; i++) {
leftMax[i] = Math.max(height[i], leftMax[i - 1]);
}
int[] rightMax = new int[n];
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; i--) {
rightMax[i] = Math.max(height[i], rightMax[i + 1]);
}
int ans = 0;
for (int i = 0; i < n; i++) {
ans += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return ans;
}
}经典面试题接雨水，先从两端分别遍历两次数组记作 leftMax 和 rightMax，每个元素记录当前遇到的最大高度，最后再从左到右遍历，每个格子能接到的雨水量就是 min(leftMax[i], rightMax[i]) – height[i]。
