三数之和

leetcode 三数之和 题目链接

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

/*** @param {number[]} nums* @return {number[][]}*/
var threeSum = function(nums) {let orderNums = nums.sort((a, b) => a - b);const result = [];
// 三数之和转变为一个固定数去寻找另外两个数for(let i = 0; i<= orderNums.length - 3; i++) {let left = i + 1;let right = orderNums.length - 1;while(left < right) {let count = orderNums[i] + orderNums[left] + orderNums[right];const array = [orderNums[i], orderNums[left], orderNums[right]]if(count > 0) {// 由于orderNums是有序的，通过调整右指针左移 调整变小 寻找下一对right --} else if (count < 0) {//由于orderNums是有序的，通过调整左指针右移 调整变大 寻找下一对left ++} else {
//                  判断是否已经有了对应的数据，不重复const have = result.find((item) => {return item.every((value, index) => value === array[index]);})if(!have) {result.push(array)}// 寻找下一对right--left ++}}}return result};

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

/*** @param {number[]} nums* @return {void} Do not return anything, modify nums in-place instead.*/
var moveZeroes = function(nums) {for(let i = 0; i < nums.length - 1; i++) {for(let j = i + 1;j < nums.length; j++) {let right = j;if(nums[i] === 0 && nums[j]!== 0) {// 交互位置,确保第i位现在不可能为0[nums[i],nums[j]] = [nums[j],nums[i]]// 然后指针i可以向右移动拉，跳出本次循环break}}}
};

盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。

说明：你不能倾斜容器。

/*** @param {number[]} height* @return {number}*/
var maxArea = function(height) {let maxArea = 0;let left = 0;let right = height.length - 1;for(let i = 0; i < height.length; i++) {for(let j = i + 1;j < height.length;j++) {let width = j - i;// 高度选最小的let heights = Math.min(height[i], height[j])const area = width * heightsmaxArea = Math.max(maxArea,area)}} return  maxArea
};

上面的写法虽然也是双指针i和j不断移动，但移动的方式不够灵活

/*** @param {number[]} height* @return {number}*/
var maxArea = function(height) {let maxArea = 0;// 两个指针的位置从距离最远开始，不断靠近let left = 0;let right = height.length - 1;while( left < right) {const heights = Math.min(height[left], height[right]);const width = right - left;const area = heights * width;maxArea = Math.max(maxArea,area)// 尽量保留高的值，参与下一轮面积的计算，将值较小的那个指针移动if(height[right] > height[left]) {left++} else {right--}}return  maxArea
};

接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
leetcode 接雨水 https://leetcode.cn/problems/trapping-rain-water/solutions/692342/jie-yu-shui-by-leetcode-solution-tuvc/?envType=study-plan-v2&envId=top-100-liked

对于下标 i，下雨后水能到达的最大高度等于下标 i 两边的最大高度的最小值，下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去 height[i]。

我们可以分别用两个for 循环，求出两部分的面积，然后再对两个数组记录的元素进行比较，取较小的值为一个新数组，最后让这个新数组减去柱子本身的高度。

var trap = function(height) {let ans = 0;// 由上图的动态规划可知，两个图加起来，取较低的值为max并减去柱子的高度// 但如果用双指针来实现更容易，一个从左往右，一个从右往左。let left = 0, right = height.length - 1;// 分别记录从左往右的最大值，和从右往左的最大值let leftMax = 0, rightMax = 0;while (left < right) {// 分别记录从左往右的最大值，和从右往左的最大值leftMax = Math.max(leftMax, height[left]);rightMax = Math.max(rightMax, height[right]);// 比较当前两个指针所指的值的大小，始终从小的那边取值if (height[left] < height[right]) {ans += leftMax - height[left];left++;} else {ans += rightMax - height[right];right--;}}return ans;
};