双指针问题
16. 最接近的三数之和
先按照升序排序,然后分别从左往右依次选择一个基础点 i
(0 <= i <= nums.length - 3
),在基础点的右侧用双指针去不断的找最小的差值。
假设基础点是 i
,初始化的时候,双指针分别是:
left
:i + 1
,基础点右边一位。right
:nums.length - 1
数组最后一位。
然后求此时的和,如果和大于 target
,那么可以把右指针左移一位,去试试更小一点的值,反之则把左指针右移。
在这个过程中,不断更新全局的最小差值 min
,和此时记录下来的和 res
。
最后返回 res
即可。
js
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var threeSumClosest = function (nums, target) {
// 排序
nums.sort((a, b) => a - b)
let min = Infinity // 目前的最小差值
let sum = 0
for (let k = 0; k < nums.length - 2; k++) {
let i = k + 1, j = nums.length - 1
while (i < j) {
let temp = nums[k] + nums[i] + nums[j]
if (temp === target) {
return target
}
if (Math.abs(target-temp)<min) {
sum = temp
min = Math.abs(target-temp)
}
if (temp < target) {
i++
}
if (temp > target) {
j--
}
}
}
return sum
};
11. 盛最多水的容器
双指针法。从左右两边开始计算面积,应用较高的线来寻找较长的范围,从而获得较大的面积。因此当左值较小时,左指针增加,右值较小时,右指针减小。
js
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
let left=0, right=height.length-1, area=0
// 终止条件:left>=right
while (left<right) {
// 每次left或者right改变后都更新area
let tempArea = (right-left)*Math.min(height[left],height[right])
area = (area<tempArea)?tempArea:area
// 判断左右木桶板的高度: 移动时保留高的木板
if (height[left]<height[right]) { // 例如此时右侧木板高, 所以保留右侧木板不动, 移动左侧木板(left++)
left++
}else {
right--
}
}
return area
};