三数之和

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 * heights
        maxArea = 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;
};