leetcode答案-Algorithms:算法

leetcode 答案 Algorithms 一、three sum 三数相加问题 问题描述 在一个由 number 组成的数组中，找到所有的 3 个数组成的数组，使得这三个数字的和等于给定的数字 解答 考虑到时间复杂度肯定大于等于 O(n²) 可以先用 sort 排序，从左到右依次增大 遍历数组，设置两个指针，一个从当前 index 开始往右，一个从最右往左，这三个值的和如果等于 target 则记录下来，如果大于则右边指针向左移动，小于则左侧指针向右移动，如果移动过程中发现值相等则直接继续移动 遍历的出口是当前值大于等于 0 二、trapping rain water 雨水收集问题 问题描述 给定一个 number 组成的数组，值代表箱子的高度，下雨后，这些箱子中的间隙一共能收集到多少雨水 解答 暴力破解： 遍历数组，找当前 index 往左的最大值和当前 index 往右的最大值 这两个值中取小的那个减去当前 index 的箱子高度就是当前位置能收集到雨水的高度 最后求和 暴力破解的优化： 从左向右遍历数组，保存当前位置和左侧最高值中的较大值 max1 从右向左遍历数组，保存当前