双指针
- 一般解决分段的问题,即求某一段的数据的值
- i为指针起点,j为指针终点
- 一种是滑动窗口,i,j一定方向相同
- 一种是夹逼,i,j相向
配合前缀和使用
a[i]+....a[j]=s[j]-s[i-1]
LeetCode
167. 两数之和 II - 输入有序数组(模板题)
给你一个下标从 1 开始的整数数组 numbers
,该数组已按 非递减顺序排列 ,请你从数组中找出满足相加之和等于目标数 target
的两个数。如果设这两个数分别是 numbers[index1]
和 numbers[index2]
,则 1 <= index1 < index2 <= numbers.length
。
以长度为 2 的整数数组 [index1, index2]
的形式返回这两个整数的下标 index1
和 index2
。
你可以假设每个输入 只对应唯一的答案 ,而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例 1:
输入:numbers = [2,7,11,15], target = 9
输出:[1,2]
解释:2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2:
输入:numbers = [2,3,4], target = 6
输出:[1,3]
解释:2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3:
输入:numbers = [-1,0], target = -1
输出:[1,2]
解释:-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
提示:
2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers
按 非递减顺序 排列-1000 <= target <= 1000
- 仅存在一个有效答案
解题思路
1. 双指针夹逼,条件:数组升序,左右和
2. 字典,来一个存一个,如果找到target-i,获取返回
完整代码
- 双指针
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function(numbers, target) {
// 使用双指针扫描
// 1. 滑动窗口 i,j方向相同
// 2 .i,j相向
// 这里 i,j相向
// 因为数组升序,i一开始最小,j一开始最大
// i+j>target i不动,j左移 ==> target 变小 ,如果满足,直接返回,如果<target 说明i要右移 target变大
// 夹逼最后找到解
let j=numbers.length-1
for(let i=0;i<numbers.length;i++){
while(i<j&&numbers[i]+numbers[j]>target){
j--
}
if(i<j&&numbers[i]+numbers[j]===target){
return [i+1,j+1]
}
}
};
- 字典
// 可以使用字典
// 每来一个元素,计算它的另一半(target-i)
// 看是否已经存在字典中
let m=new Map()
for(let i=0;i<numbers.length;i++){
let j=target-numbers[i]
if(m.has(j)){
return [m.get(j),i+1]
}else{
m.set(numbers[i],i+1)
}
}
15. 三数之和
给你一个整数数组 nums
,判断是否存在三元组 [nums[i], nums[j], nums[k]]
满足 i != j
、i != k
且 j != k
,同时还满足 nums[i] + nums[j] + nums[k] == 0
。请
你返回所有和为 0
且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。
示例 2:
输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。
示例 3:
输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 。
提示:
3 <= nums.length <= 3000
-105 <= nums[i] <= 105
解题思路
1. 三数之和,转换为两个两数之和
完整代码
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
// 解题思路
// 转换为两个两个之和
// nums[i]+nums[j]+nums[k]===0
// nums[j]+nums[k]===-nums[i]
// 先对nums进行排序,因为后面的两数之和算法需要有序
nums.sort((a,b)=>a-b)
// console.log(nums)
let res=[]
for(let i=0;i<nums.length;i++){
// start为开始下标,因为i<j<k
// 有序数组的去重 ==> nums[i] 相等时只需要计算一次
if(i>0&&nums[i]===nums[i-1]) continue
let result=twoSum(nums,i+1,-nums[i])
result.forEach(item=>{
res.push(item)
})
}
return res
};
var twoSum = function(numbers, start,target) {
// 使用双指针扫描
// 1. 滑动窗口 i,j方向相同
// 2 .i,j相向
// 这里 i,j相向
// 因为数组升序,i一开始最小,j一开始最大
// i+j>target i不动,j左移 ==> target 变小 ,如果满足,直接返回,如果<target 说明i要右移 target变大
// 夹逼最后找到解
let j=numbers.length-1
let res=[]
for(let i=start;i<numbers.length;i++){
// 这里也需要去重,即nums[j] 相同时,没有必要重复计算
if(i>start&&numbers[i]===numbers[i-1]) continue
while(i<j&&numbers[i]+numbers[j]>target){
j--
}
if(i<j&&numbers[i]+numbers[j]===target){
// 这里返回的为数组的数组,存储nums[i] 固定时,j,k的组合
// return [i+1,j+1]
res.push([-target,numbers[i],numbers[j]])
}
}
return res
};
- 注意点
- 需要对数组进行排序
- 需要去除重复项
11. 盛最多水的容器
给定一个长度为 n
的整数数组 height
。有 n
条垂线,第 i
条线的两个端点是 (i, 0)
和 (i, height[i])
。
找出其中的两条线,使得它们与 x
轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明:你不能倾斜容器。
示例 1:
输入:[1,8,6,2,5,4,8,3,7]
输出:49
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
示例 2:
输入:height = [1,1]
输出:1
提示:
n == height.length
2 <= n <= 105
0 <= height[i] <= 104
完整代码
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
// 解题思路
// 双指针夹逼
// 木桶水的容量由短的那块木板决定
// 刚开始 res=(j-i)*h[短]
// 如果长的木板舍弃掉,往里夹逼,容量一定减小(j-i变小,而短木板没动)
// 如果短木板舍弃,往里夹逼,(j-i变小) ,容量可能增大(短的木板下一位可能比之前的长,上限变高)
// 所以我们每次舍弃短的木板,求哪个最大
let i=0
let j=height.length-1
let max=0
while(i<j){
// 短的木板内移
if(height[i]<height[j]){
max=Math.max(max,height[i]*(j-i))
i++
}else{
max=Math.max(max,height[j]*(j-i))
j--
}
}
return max
};
84. 柱状图中最大的矩形(单调栈模板)
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
示例 1:
输入:heights = [2,1,5,6,2,3]
输出:10
解释:最大的矩形为图中红色区域,面积为 10
示例 2:
输入: heights = [2,4]
输出: 4
提示:
1 <= heights.length <=105
0 <= heights[i] <= 104
解题思路
1.可以使用暴力枚举,但是O(n*b)
从当前矩形往左右扩散
可以相连则计算一下最值
循环全部矩形,重复上述操作
2. 单调栈解法
for 矩形
保留递增的矩形(入栈)
遇到递减的(计算递增矩形序列中的最值,pop递增矩形)
插入该递减的值
重新构成了递增的矩形序列,重复上述操作
- 计算递增矩形序列最值
完整代码
/**
* @param {number[]} heights
* @return {number}
*/
var largestRectangleArea = function(heights) {
// 单调栈解决
// 如果后面的数递增,入栈,
// 遇到递减的,我们开始计算之前单调栈的最值,pop值,直到小于新的值,新值入栈
// 再次变成了单调栈,重复上述操作
let stack=[]
// 写一个临界条件
// 最后一个值为0
// 用于终止递增的单调栈
heights.push(0)
let res=0
for(let i=0;i<heights.length;i++){
let account_width=0
// console.log(heights[i])
// 当不递增时
while(stack.length&&(stack[stack.length-1].height>=heights[i])){
// 从最高点的开始往左扩散
// width上升
account_width+=stack[stack.length-1].width
// console.log(stack)
res=Math.max(res,account_width*stack[stack.length-1].height)
stack.pop()
}
// 递增,入栈
// 这里account_width 要加上去,因为原来在栈中的被pop出去了
stack.push({width:account_width+1,height:heights[i]})
}
return res
};
239. 滑动窗口最大值(单调队列模板题)
给你一个整数数组 nums
,有一个大小为 k
的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k
个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1:
输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2:
输入:nums = [1], k = 1
输出:[1]
提示:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length
完整代码
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function(nums, k) {
// 解题思路
// 维护一个单调递减的队列
// 因为后面插入的数如果大于前面的,说明前面的数是不是没用了,当前窗口的最大值为后插入的数
// 所以pop 前面的数,直到递减序列,这样可以保证队头为最大值
// 同时队头可能越界,不在窗口中,需要出队
let deQueue=[]
let res=[]
for(let i=0;i<nums.length;i++){
// 需要判断队头是否出界了
// dequeue存放的为下标,i-k为滑动串口的起点
while(deQueue.length&& deQueue[0]<=i-k) deQueue.shift()
// 存放单调递减的序列
while(deQueue.length&& nums[deQueue[deQueue.length-1]]<=nums[i]) deQueue.pop()
deQueue.push(i)
if(i>=k-1){
res.push(nums[deQueue[0]])
}
}
return res
};
标签:target,nums,示例,number,差分,let,numbers,指针,前缀
From: https://www.cnblogs.com/lingxin1123/p/17087588.html