跟着灵茶山艾府大佬学习算法思路的day1，目标是在一个月内掌握hot100
b站链接如下：
三数之和题目描述：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
给你一个整数数组 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 。
思路：
根据二数之和的思路，当数组有序（升序或降序，默认升序），如果数组头部和尾部的值之和大于target，那么尾部的值与其余任何值之和也都大于target，因此头部指针不移动，将尾部指针向前移动一步（将总值变小），再进行判断。如果小于target，则尾部指针不动，将头部指针向前一步（将总值变大）。当等于target时，就可以返回。这样最终的复杂度是o(n)。
三数之和是二数之和的升级版，可以通过二层循环来完成。外层循环控制i的前进，每一次外层循环中，原问题中的target-nums[i]都是确定的一个值，此时这个新值可以被视为二数之和问题中的target。内层循环就可以进行二数之和的思路，将j和k的总和逐步与新值匹配，如果没有匹配的值，就退出内层循环，回到外层循环，将i前进。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
var threeSum = function(nums) {
const result = [];
const n = nums.length;
if (n < 3) return [];
// 数组长度小于3，无法返回三元组
nums.sort((a, b) => a - b);
// js排序函数，如不传入参数默认将数字转为字符串后比较
for(let i = 0; i < n - 2; i++) {
if (nums[i] > 0) break;
// 如果排序完第一个数就大于零，那就直接退出
if (i > 0 && nums[i] === nums[i - 1]) {
continue;
// 跳过对于i来说会出现的重复值
}
let j = i + 1;
let k = n - 1;
const target = 0 - nums[i];
// 用target模拟二数之和
while (j < k) {
if (nums[j] + nums[k] === target) {
result.push([nums[i], nums[j], nums[k]]);
// 返回目标三元组
while (j < k && nums[j] === nums[j + 1]) j++;
while (j < k && nums[k] === nums[k - 1]) k--;
// 题目要求不能返回重复的三元组，要跳过j和k的重复值
j++;
k--;
// 找到一组三元组之后，如果只变更一端的值，就不可能得到新的目标三元组
}
else if (nums[j] + nums[k] > target) {
k--;
}
else {
j++;
}
}
}
return result;
};
总结：
总体思路其实不算特别复杂，从二数之和到三数之和的思路演进都比较好理解，但在实际编辑代码时有不少边界条件是需要注意的，例如可能出现的重复值，这一问题对于ijk三个值来说都是可能出现的。
盛水最多的容器题目描述：
1
2
3
4
5
6
7
给定一个长度为 `n` 的整数数组 `height` 。有 `n` 条垂线，第 `i` 条线的两个端点是 `(i, 0)` 和 `(i, height[i])` 。
找出其中的两条线，使得它们与 `x` 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
**说明：**你不能倾斜容器。
示例 1：
1
2
3
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：
1
2
输入：height = [1,1]
输出：1
思路：
容器所能盛水量由两条线中最短的线和两条线之间的距离决定，我们可以根据最前的线和最后的线初始化盛水量的初始值。一般来说，初始两条线中会有一条线较短，如果此时将较长的线向内移动，可能会遇到比原先较短的线更长或者更短的线，但无论遇到哪种线段，两条线之间的距离一定是逐步缩短的，盛水的高度也不可能再高于原先较短的线，所以我们在记录完盛水量之后，可以直接将较短的线段去掉。如果出现两条线一样长的情况，那么移动哪一条都可以。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var maxArea = function(height) {
const n = height.length;
let left = 0;
let right = n - 1;
let size = 0;
while (left < right) {
const current = (right - left) * Math.min(height[left], height[right]);
size = Math.max(current, size);
if (height[left] > height[right]) {
right--;
}
else {
left++;
}
}
return size;
};
总结：
这道题主要是难在思路构建，只要把每次都只去掉较短那一根线这点想明白，代码实现非常简单，也没有什么特殊的边界判定。
接雨水题目描述：
1
给定 `n` 个非负整数表示每个宽度为 `1` 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
1
2
3
输入：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：
1
2
输入：height = [4,2,0,3,2,5]
输出：9
思路：
可以将每一间隔间的区域先分开独立看待，看作是若干个不同的木桶，这些木桶的底座和两边的高度各不相同。每个木桶的左侧高度取决于木桶左边的最大高度，右侧木板同理，最后计算公式会是如此格式：（最后木桶所盛水量就是左右侧高度的较小值-木板底座高度）*宽度（此时宽度一定为1）。最后将所有的木桶容量相加，就是所能接到的雨水量。
那么在将问题初步拆分后，下一个问题就是如何计算，或者说记录左右侧木板的高度。可以考虑用两个数组来存储各个木桶的前缀最大值和后缀最大值。对于每个前缀或者后缀最大值，可以用新的前缀或者后缀值与最新值比较，将更大者更新进最大值。从头遍历和从尾遍历，就能得到前缀最大值和后缀最大值数组，最后再同时遍历这两个数组，取出每个木桶的较短边，再减去木桶底部高度，就是每个木桶的容量。
显然，上面这种方法的时间复杂度和空间复杂度均为o(n)。
但在空间上还可以优化，在计算前缀最大值和后缀最大值时，我们不必要得到所有木桶的所有前缀和后缀最大值才能开始计算，在计算进行到途中时，只要我们知道一个木桶一侧的高度（假设是左侧），那么无论右侧的后缀最大值遍历到哪了，只要此最值高度大于已知的左侧高度，木桶的容量也实际上已经被左侧高度所决定了。在计算完这个木桶的容量之后，前缀最大值也可以向右继续遍历扩展了。
一句话总结，如果左边木桶的前缀最大值比已经算出的后缀最大值要小，那么容量由前缀最大值决定，计算完容量后可以略过此木桶向后扩展；如果右边木桶的后缀最大值比已经算出的前缀最大值小，那么计算完容量后就略过此木桶向前扩展。
这种方法不需要额外创建数组，空间复杂度就可以缩减为o(1)。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var trap = function(height) {
const n = height.length;
let preMax = 0;
let postMax = 0;
let left = 0;
let right = n - 1;
let size = 0;
while (left < right) {
preMax = Math.max(preMax, height[left]);
postMax = Math.max(postMax, height[right]);
// 每次循环时会先更新前缀最大值和后缀最大值
// 如果当前高度小于最大值，那么能装水
// 如果当前高度大于最大值，那么最大值就会被更新为当前高度，当然也无法装水
if (preMax < postMax) {
size += (preMax - height[left]);
left++;
}
else {
size += (postMax - height[right]);
right--;
}
}
return size;
};
总结：
不愧为困难题，最一开始对于木桶的理解已经比较抽象了，没有做过的话基本不太可能想得出来，对于最优解的构建就更加复杂一些，需要反复理解。