前缀和双指针
题目要求 连续有序子序列，求最大子序列，存在进出条件，滑动窗口
题目要求 连续无序子序列，无法预测数组趋势，找子区间和，前缀和
滑动窗口要求新加数据A之后，后续再加数据B不会使得A符合条件(可预测趋势，如递增)
前缀和不需要
注意 Array.sort() 默认排序结果为根据Unicode码。
会出现[-1, -1, -4, 0, 1, 2]这种奇怪的结果
传入的函数返回 小于0 的数则不交换，(a,b)=>a-b 代表从小到大排序
1. 删除子数组的最大得分（ LeetCode 1695 ）
var maximumUniqueSubarray = function (nums) {
let start = end = 0
let max = sum = 0
let map = {}
const l = nums.length
// 滑动窗口，每次要放入元素前，先判断前端是否要弹出元素
for(let end = 0; end < l; end++) {
while(map[nums[end]]) {
sum -= nums[start]
delete map[nums[start]]
start++
}
sum += nums[end]
map[nums[end]] = true
max = Math.max(max,sum)
}
return max
};2. 最大子数组和（ LeetCode 53 ）
前缀和
var maxSubArray = function(nums) {
let pre = 0, maxAns = nums[0];
nums.forEach((x) => {
// pre 表示以第 i 个元素结尾的最大子数组的和
// 此处循环是模拟向数组中一个个添加元素
// 每添加一次求出其maxAns，直到加到和nums一样。
// [a] 中加入b，若pre小于0，则b自己就是最大子数组
// [a, b] 中加入c，若pre大于0，则pre+c为最大子数组
// 一个个添入
pre = Math.max(pre + x, x); // pre可能为第i个数，也可能为连续前n个数的和，必然符合连续子序列
// 顺便算一下每添加一个元素时，数组的maxAns
maxAns = Math.max(maxAns, pre);
});
return maxAns;
};3. 三数之和（ LeetCode 15 ）
双指针
方法一，两次去重思路一致，心智负担更小
// 本质是三重循环的优化版，关键点是排序，先确定第一个数i，内部两层循环改为双指针
// 2次去重:i元素相同，跳过去重；left元素相同，跳过去重
// 2次提前结束:i元素>0，结束i循环；没找到right使三者合<=0，结束left循环
var threeSum = function (nums) {
const result = []
const l = nums.length
if (l < 3) return result
nums.sort((a, b) => a - b)
for (let i = 0; i < l; i++) {
if (nums[i] > 0) break // nums[i] > 0 则三个数必然都大于0
// i 去重，和上一次循环的数相同的话，其情况必然是遍历过的
if (i > 0 && nums[i] === nums[i - 1]) continue
let right = l - 1
for (let left = i + 1; left < l; left++) {
// left 去重，和上一次循环的数相同的话，其情况必然是遍历过的
if (left > i + 1 && nums[left] == nums[left - 1]) continue;
// 确定了i left,及其去重，后续只考虑找 right，三者之和大于0，说明需要找更小的数
while (left < right && nums[i] + nums[left] + nums[right] > 0) right--
// 指针重合代表 i left 没找到right 三者合 <= 0的，left再大也没用，直接退出循环
if (left === right) break;
if (nums[i] + nums[left] + nums[right] === 0) {
result.push([nums[i], nums[left], nums[right]])
}
}
}
return result
};方法二
// 本质是三重循环的优化版，关键点是排序，先确定第一个数i，内部两层循环改为双指针
// 两层去重:i元素相同，跳过去重；left/right元素相同，跳过去重
var threeSum = function (nums) {
const result = []
const l = nums.length
if (l < 3) return result
nums.sort((a, b) => a - b)
for (let i = 0; i < l; i++) {
// 如果nums[i] > 0 则三个数必然都大于0,合不可能===0
if (nums[i] > 0) break
// if(nums[i] === nums[i+1]) i++,这里不可以采取跳过的形式，直接跳过相当于少了一个元素
if (i > 0 && nums[i] === nums[i - 1]) continue
let left = i + 1
let right = l - 1
while (left < right) {
let sum = nums[i] + nums[left] + nums[right]
if (sum === 0) {
result.push([nums[i], nums[left], nums[right]])
// 1.去重，如[-2,0,0,2,2]，i指向的元素为2时用两种解。
while (left < right && nums[left] == nums[left + 1]) left++
while (left < right && nums[right] == nums[right - 1]) right--
// 2.left right都需要变动，因为[a,b,c]中确定了ab，c也就确定了，再次找出的C会重复
// 2.另外同时，由于1情况的存在，所以还是需要1这步去重
left++
right--
} else if (sum < 0) {
left++; // 三者之和小于 0，说明需要找更大的数
} else if (sum > 0) {
right--; // 三者之和大于0，说明需要找更小的数
}
}
}
return result
};4.盛最多水的容器(LeetCode 11)
双指针
双99%击败
var maxArea = function(height) {
let start = 0,end = height.length -1,result = - Number.MAX_VALUE
while(start < end) {
if(height[start] < height[end]) { // 谁小谁就是height
if(height[start] * (end - start) > result) {
result = height[start] * (end - start)
}
// 小的往区间内部走，找比start更高的柱子，更矮的必然面积更小，直接略过
while(start + 1 < end && height[start + 1] < height[start]) {
start ++
}
start ++
} else {
if(height[end] * (end - start) > result) {
result = height[end] * (end - start)
}
// 小的往区间内部走，找比end更高的柱子，更矮的必然面积更小，直接略过
while(start < end - 1 && height[end - 1] < height[end]) {
end --
}
end --
}
}
return result
};5.和为 K 的子数组(LeetCode 560)
前缀和,找区间和
由于不关心i，所以没必要用数组储存前缀和，不储存i，只需要计数
var subarraySum = function (nums, k) {
let result = 0
let pre = 0
const map = {}
const l = nums.length
for(let i = 0; i < l; i++) {
}
let result = 0
for(let i = 0; i < l)
};
