11. 盛最多水的容器

题目描述 给定 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。 说明:你不能倾斜容器,且 n 的值至少为 2。 图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。 示例: 输入: [1,8,6,2,5,4,8,3,7] 输出: 49 https://leetcode-cn.com/problems/container-with-most-water/ 解法1 解法1使用暴力法,使用变量i,j(i<j)指向每一个挡板,计算res = max(res, (j-i)*min(height[i], height[j]))。时间复杂度O(n^2), 空间复杂度O(1)。 解法2 在解法1中,我们遍历了每一对挡板。其实,我们完全不必要计算每一对挡板产生的容积,我们只需要遍历一遍就能够计算出答案。例如{2,3,5,1,7},在解法1中第一次循环我们计算{<2,3>, <2,5>, <2,1>, <2,7>}。题目要求我们求得最大的容积,其实我们计算<2,7>就够了,如果我们用其他组合计算容积,首先宽度会减少;其次容积取决于短板,即使在2与7之间有更长的木板,那么我们也只能用最短的木板2来计算容积。 根据上面的分析,我们使用双指针法来解决问题。使用变量i,j指向数组height的两端。计算res = max(res, (j-i)*min(height[i], height[j])),然后将i与j中指向短板的那一个指针向内移动。即,height[i] > height[j], 则j–;如果height[i] < height[j],则i++;如果二者相等,先移动哪一个都无所谓。 解释: 首先,我们让i与j指向height的两端,能够保证容器容器的宽度(j-i)尽可能的宽。其二,容器装水量取决于两端height[i]与height[j]较短者,所以有上面的公式。其三,计算完当前容积后,我们应该淘汰二者较短的那一个,因为我们没有理由淘汰长板。如果我们淘汰长板,那么随着宽度的减少,左右挡板的高度变化趋势是下降的,这样会使得容积更小。

Read more

16. 最接近的三数之和

题目描述 给定一个包括 n 个整数的数组 nums和 一个目标值 target。找出 nums中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。 例如,给定数组 nums = [-1,2,1,-4], 和 target = 1. 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2). https://leetcode-cn.com/problems/3sum-closest/ 解法1 这道题目与三数之和非常相似, 不同之处在于本题要求解的是最接近目标值的三数之和而不要求三数之和为0. 另一个不同点是, 题目给定的输入能保证只存在唯一答案. 我们还是使用“三数之和”解法1的做法, 首先将数组nums排序,以降低内层循环的时间复杂度. 变量i依次访问数组nums的每个元素, 作为外层循环. 内层循环中, 我们用j, k指针分别指向i之后数组的两端. 我们将nums[i]+nums[j]+nums[k]与target之差的绝对值记为diff, diff的初值为Integer.MAX_VALUE. 如果nums[i]+nums[j]+nums[k]与target之差的绝对值小于diff, 则更新diff. 题目要求nums[i]+nums[j]+nums[k]的和, 那么我们除了记录diff之外, 还应该记录与diff对应的三个数之和, 我们计作threeSum. 现在我们分析下如何维护变量j与k. 如果三个数之和小于target, 那么说明我们要找更大的数才能使三数之和更接近target, 所以j自增1. 如果三数之和大于target, 说明我们从右边选的数太大了, 应该k自减1. 如果三数之和与target相等, 那么三数之和与target的差距是0, 这是最接近target的情况了. 注意, 如果遇到这种情况,…

Read more

15. 三数之和

题目描述 给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。 注意:答案中不可以包含重复的三元组。 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4], 满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ] https://leetcode-cn.com/problems/3sum/ 解法1 首先对原数组nums进行排序, 用指针i指向nums的每个元素, 然后另指针j=i+1, k=|nums|-1. 指针j与k相向而行, 直到nums[i]+nums[j]+nums[k] == 0我们就找到了一个解, 此时需要继续相向而行直到k>=j. 将数组排序可以把算法的时间复杂度降低到O(n^2). 若不对数组排序, 为了寻找j, k使得nums[i]+nums[j]+nums[k] == 0, 需要使用双重循环遍历nums, 这样会使复杂度达到O(n^3). 因为题目要求“不可以包含重复的三元组”, 这就需要我们一旦找到符合条件的i, j, k. 就需要跳过nums中相同的元素(代码中被标记的部分), 以避免寻找重复的解. 例如…

Read more