双指针秒杀7道数组题
26.删除有序数组中的重复项
设置快慢指针，比较快慢指针，符合条件时慢指针才移动
var removeDuplicates = function(nums) {let slow = 0let fast = 1while (fast < nums.length) {if (nums[fast] != nums[slow]) {nums[++slow] = nums[fast]}fast ++}// 返回长度 下标加 1return slow + 1};
83.删除排序链表中的重复元素
var deleteDuplicates = function(head) {if (head === null) return headlet slow = headlet fast = headwhile (fast !== null) {if (fast.val != slow.val) {slow.next = fastslow = slow.next}fast = fast.next}slow.next = nullreturn head};
27.移除元素
var removeElement = function(nums, val) {
let slow = 0
let fast = 0
while (fast < nums.length) {
if (nums[fast] !== val) {
nums[slow ++] = nums[fast] // slow ++
}
fast ++
}
return slow
};
283.移动零
var moveZeroes = function(nums) {
let slow = 0
let fast = 0
while (fast < nums.length) {
if (nums[fast] !== 0) {
nums[slow ++] = nums[fast]
}
fast ++
}
while (slow < nums.length) {
nums[slow ++] = 0
}
return nums
};
167. 两数之和 II - 输入有序数组
var twoSum = function(numbers, target) {
let l = 0
let r = numbers.length - 1
while (l < r) {
const sum = numbers[l] + numbers[r]
if (sum === target) {
return [l + 1, r + 1]
}
if (sum < target) {
l ++
} else {
r --
}
}
return [-1, -1]
};
344. 反转字符串
// 思路： 头尾指针，相遇之前交换值
var reverseString = function(s) {
for (let i = 0, j = s.length - 1; i < j; i++, j--) {
[s[i], s[j]] = [s[j], s[i]]
}
return s
};
5. 最长回文子串
找回文串的难点在于，回文串的的长度可能是奇数也可能是偶数，解决该问题的核心是从中心向两端扩散的双指针技巧
var longestPalindrome = function(s) {
// 在 s 中寻找以 s[l] 和 s[r] 为中心的最长回文串
const palindrome = (s, l, r) => {
while (l >= 0 && r < s.length && s[l] === s[r]) {
l --
r ++
}
return s.substring(l + 1, r)
}
let res = ''
for (let i = 0; i < s.length; i ++) {
// 奇数： 以 s[i] 为中心的最长回文子串
const s1 = palindrome(s, i, i)
// 偶数：以 s[i] 和 s[i+1] 为中心的最长回文子串
const s2 = palindrome(s, i, i + 1)
// res = longest(res, s1, s2)
res = res.length > s1.length ? res : s1
res = res.length > s2.length ? res : s2
}
return res
};
前缀和数组
560. 和为 K 的子数组
前缀和主要适用的场景是原始数组不会被修改的情况下，频繁查询某个区间的累加和。
构建一个前缀和数组, preSum[i + 1] = preSum[i] + nums[i], nums数组区间[i, j]内的数组和为preSum[j + 1] - preSum[i]
例如数组[1, 1, 1]的前缀和数组为[0, 1, 2, 3]，区间[0, 1]间的数组和为2(2 - 0)
var subarraySum = function(nums, k) {
const preSum = new Array(nums.length + 1).fill(0)
// 得到前缀和数组:eg. [1, 1, 1] => [0, 1, 2, 3]
for (let i = 0; i < nums.length; i ++) {
preSum[i + 1] = preSum[i] + nums[i]
}
let res = 0
// 计算区间和为k的数目
for (let i = 0; i < preSum.length; i ++) {
for (let j = i + 1; j < preSum.length; j ++) {
if (preSum[j] - preSum[i] === k) {
res ++
}
}
}
return res
};
以上写法时间复杂度为O(N^2), 嵌套循环可看做求出有多少个 i 满足preSum[i] = preSum[j] - k，因此可以用哈希表优化
[1, 1, 1] ,k = 2
前缀和数组为[0, 1, 2（0）, 3（1）] , 只需找到preSum[i] - k 的前缀和出现次数即可
var subarraySum = function(nums, k) {
let preSum = 0
// 前缀和 -> 该前缀和出现的次数
let hash = {
0: 1 // basecase：和为 0 的默认就为 1
}
let res = 0
for (let i = 0; i < nums.length; i ++) {
// 累加前缀和
preSum += nums[i]
if (hash[preSum - k]) {
res += hash[preSum - k]
}
hash[preSum] = hash[preSum] ? hash[preSum] + 1: 1
}
return res
};
差分数组
差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减
eg. 差分数组：[8, 2, 6, 3, 1] => [8, - 6, 4, -3, -2]
实现一个差分类
class Difference {
constructor (nums) {
// 构建差分数组
this.diff = [nums[0]]
for (let i = 1; i < nums.length; i ++) {
this.diff[i] = nums[i] - nums[i - 1]
}
}
// 区间[i, j]内增加一个数值 val 可为负数
increment (i, j, val) {
// [i...] 区间内所有元素都增加val
this.diff[i] += val
if (j + 1 < this.diff.length) {
// [j...]区间内所有元素都减少val => [i, j]区间内增加val
this.diff[j + 1] -= val
}
}
// 根据差分数组构造结果数组
getRes () {
let res = [this.diff[0]]
for (let i = 1; i < this.diff.length; i ++) {
res[i] = res[i - 1] + this.diff[i]
}
return res
}
}
let diffArr = new Difference([3, 2, 1])
diffArr.increment(0, 1, 2)
diffArr.getRes()
1109. 航班预订统计
相当于[1, 2]区间增加10航班, [2, 3]区间增加20航班, [2, 5]区间增加25航班
var corpFlightBookings = function(bookings, n) {
let nums = new Array(n).fill(0)
// 实现一个差分类
let diff = new Difference(nums)
bookings.map(([i, j, val]) => {
// 航班从 1 算起，下标从 0 算起
diff.increment(i - 1 ,j - 1, val)
})
return diff.getRes()
};
1094. 拼车
算出所有区间内，车内所有乘客数，再比较是否超载即可
var carPooling = function(trips, capacity) {
// 最多1000个车站
let nums = new Array(1001).fill(0)
let diff = new Difference(nums)
trips.map(([val, i, j]) => {
// 乘客在[i, j)在车内
diff.increment(i, j - 1, val)
})
// 得到所有区间内车内乘客数
const res = diff.getRes()
// 任意区间内都不该超载
return res.every(i => i <= capacity)
};
旋转二维数组
48.旋转图像
顺时针反转90度：先沿对角线对称反转，再每行反转
逆时针反转90度：选择另一条对角线对称反转，再每行反转
var rotate = function(matrix) {
// 1. 沿对角线对称二维矩阵
const n = matrix.length
for (let i = 0 ;i < n; i ++) {
for (let j = i; j < n; j ++) {
[matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]]
}
}
/* 反转数组 */
const reverseArr = (arr) => {
let l = 0
let r = arr.length - 1
while (l < r) {
[arr[l], arr[r]] = [arr[r], arr[l]]
l ++
r --
}
}
// 2. 每行反转
for (let i = 0; i < n; i ++) {
reverseArr(matrix[i])
}
};
54.螺旋矩阵
核心用右、下、左、上顺序遍历，并用 4 个变量圈定未遍历元素的边界
var spiralOrder = function(matrix) {
let res = []
const [m, n]= [matrix.length, matrix[0]?.length]
// 定义边界变量
let [upper, lower, left, right] = [0, m - 1, 0, n - 1]
while (res.length < m * n) {
if (upper <= lower) {
// 顶部：从左到右
for (let i = left; i <= right; i ++) {
res.push(matrix[upper][i])
}
// 顶部边界下移
upper ++
}
if (left <= right) {
// 右侧： 从上到下
for (let i = upper; i <= lower; i ++) {
res.push(matrix[i][right])
}
// 右侧边界左移
right --
}
if (upper <= lower) {
// 底部：从右到左
for (let i = right; i >= left; i --) {
res.push(matrix[lower][i])
}
// 底部边界上移
lower --
}
if (left <= right) {
// 左侧： 从下到上
for (let i = lower; i >= upper; i --) {
res.push(matrix[i][left])
}
// 左边界右移
left ++
}
}
return res
};
59.螺旋矩阵II
var generateMatrix = function(n) {
let matrix = new Array(n);
for (let i = 0; i < n; i ++) {
matrix[i] = Array(n).fill(0)
}
let num = 1
let [upper, lower, left, right] = [0, n - 1, 0, n - 1]
while (num <= n * n) {
if (upper <= lower) {
// 顶部：从左到右
for (let i = left; i <= right; i ++) {
matrix[upper][i] = num ++
}
// 顶部边界下移
upper ++
}
if (left <= right) {
// 右侧： 从上到下
for (let i = upper; i <= lower; i ++) {
matrix[i][right] = num ++
}
// 右侧边界左移
right --
}
if (upper <= lower) {
// 底部：从右到左
for (let i = right; i >= left; i --) {
matrix[lower][i] = num ++
}
// 底部边界上移
lower --
}
if (left <= right) {
// 左侧： 从下到上
for (let i = lower; i >= upper; i --) {
matrix[i][left] = num ++
}
// 左边界右移
left ++
}
}
return matrix
};
滑动窗口
76. 最小覆盖子串
取[left, right)左闭右开区间作为窗口，
先不断增大right指针直到窗口满足t（target）条件
此时停止增加right指针，转而增加left指针，更新窗口，以缩减窗口。
重复以上步骤，知道right到达s字符串的尽头(s.length)
var minWindow = function(s, t) {
// need记录 t 中字符出现次数，slideWindow记录窗口中字符出现次数
let need = {}
let slideWindow = {}
let left = 0
let right = 0
// valid: 窗口中满足 need 条件的字符个数
// 当valid === Object.keys(need).length 则说明窗口已满足条件，已经完全覆盖了串 T。
let valid = 0
// 结果记录, 用于截取字符串
let startIndex = 0
let endIndex = Infinity
// 统计t字符串的字母分布
for (let i = 0; i < t.length; i ++) {
need[t[i]] = need[t[i]] ? need[t[i]] + 1 : 1
}
// 区间左闭右开[left, right)
while (right < s.length) {
let wr = s[right ++]
slideWindow[wr] = slideWindow[wr] ? slideWindow[wr] + 1 : 1
if (slideWindow[wr] === need[wr]) {
valid ++
}
// 缩减窗口条件
while (valid === Object.keys(need).length) {
// 结果处理
if (right - left < endIndex - startIndex) {
startIndex = left
endIndex = right
}
// 左指针移动，更新窗口
let wl = s[left ++]
if (need[wl]) {
if (slideWindow[wl] === need[wl]) {
valid --
}
slideWindow[wl] --
}
}
}
return endIndex === Infinity ? '' : s.slice(startIndex, endIndex)
};
567. 字符串的排列
var checkInclusion = function(s1, s2) {
// need记录 s1 中字符出现次数，slideWindow记录[窗口]中字符出现次数
let need = {}
let sildeWindow = {}
let left = 0
let right = 0
// valid: 窗口中满足 need 条件的字符个数
// 当valid === Object.keys(need).length 则说明窗口已满足条件，已经完全覆盖了串 T。
let valid = 0
for (let i = 0; i < s1.length; i ++) {
need[s1[i]] = need[s1[i]] ? need[s1[i]] + 1 : 1
}
let res = false
// 区间左闭右开[left, right)
while (right < s2.length) {
let wr = s2[right ++]
sildeWindow[wr] = sildeWindow[wr] ? sildeWindow[wr] + 1 : 1
if (sildeWindow[wr] === need[wr]) {
valid ++
}
// 缩减窗口条件
while (right - left >= s1.length) {
// 结果处理
if (valid === Object.keys(need).length) {
res = true
break
} else {
// 左指针移动，更新窗口
const wl = s2[left ++]
if (need[wl]) {
if (sildeWindow[wl] === need[wl]) {
valid --
}
sildeWindow[wl] --
}
}
}
}
return res
};
438. 找到字符串中所有字母异位词
var findAnagrams = function(s, p) {
// need记录 p 中字符出现次数，slideWindow 记录[窗口]中字符出现次数
let need = {}
let slideWindow = {}
let left = 0
let right = 0
let valid = 0
let res = []
for (let i = 0; i < p.length; i ++) {
need[p[i]] = need[p[i]] ? need[p[i]] + 1 : 1
}
while (right < s.length) {
const r = s[right ++]
slideWindow[r] = slideWindow[r] ? slideWindow[r] + 1 : 1
if (slideWindow[r] === need[r]) {
valid ++
}
// 判断左侧窗口是否要收缩
while (right - left >= p.length) {
// 结果处理
if (valid === Object.keys(need).length) {
res.push(left)
}
// 缩减窗口
const l = s[left ++]
if (need[l]) {
if (slideWindow[l] === need[l]) {
valid --
}
slideWindow[l] --
}
}
}
return res
};
3. 无重复字符的最长子串
var lengthOfLongestSubstring = function(s) {
let slideWindow = {}
let left = 0
let right = 0
let res = 0
while (right < s.length) {
const r = s[right ++]
slideWindow[r] = slideWindow[r] ? slideWindow[r] + 1 : 1
// 缩减条件：存在重复字符
while (slideWindow[r] > 1) {
const l = s[left ++]
slideWindow[l] --
}
res = Math.max(res, right - left)
}
return res
};
二分查找
分析二分查找代码时，不要出现 else，全部展开成 else if 方便理解
/ ** 常规二分搜索 **/
const binaryBound = (nums, target) => {
// 记录数组的起始和结尾下标
let left = 0
let right = nums.length - 1
// 搜索区间为[left, right]
while (left <= right) {
const mid = Math.floor((left + right) / 2)
if (nums[mid] === target) {
// 直接返回结果
return mid
} else if (nums[mid] > target) {
right = mid - 1
} else if (nums[mid] < target) {
left = mid + 1
}
}
return -1
}
/ ** 左侧边界二分搜索 **/
const leftBound = (nums, target) => {
// 记录数组的起始和结尾下标
let left = 0
let right = nums.length - 1
// 搜索区间为[left, right]
while (left <= right) {
const mid = Math.floor((left + right) / 2)
if (nums[mid] === target) {
// 收缩右侧边界
right = mid - 1
} else if (nums[mid] > target) {
right = mid - 1
} else if (nums[mid] < target) {
left = mid + 1
}
}
// 处理target不在nums内的情况
if (left > nums.length || nums[left] !== target) {
return -1
}
return left
}
/ ** 右侧边界二分搜索 **/
const rightBound = (nums, target) => {
// 记录数组的起始和结尾下标
let left = 0
let right = nums.length - 1
// 搜索区间为[left, right]
while (left <= right) {
const mid = Math.floor((left + right) / 2)
if (nums[mid] === target) {
// 收缩左侧边界
left = mid + 1
} else if (nums[mid] > target) {
right = mid - 1
} else if (nums[mid] < target) {
left = mid + 1
}
}
// 处理target不在nums内的情况
if (right < 0 || nums[right] !== target) {
return -1
}
return right
}
console.log(rightBound([1,2,2,2,2,3], 2)) // 4
704.二分查找
var search = function(nums, target) {
return binaryBound(nums, target)
};
34. 在排序数组中查找元素的第一个和最后一个位置
var searchRange = function(nums, target) {
const left = leftBound(nums, target) // 获取左侧边界下标
const right = rightBound(nums, target) // 获取右侧边界下标
return [left, right]
};
69. x的平方根
题示是求平方根，实际是[0, x]区间内其平方最接近x的数。相当于求二分法的右边界
var mySqrt = function (x) {
let [left, right] = [0, x]
while (left <= right) {
const mid = Math.floor((l + r) / 2) // 中间位置索引 x>>1 表示除以2并取整，缩小一下遍历的范围
if (mid * mid <= x) {
left = mid + 1
} else {
right = mid - 1
}
}
return right
};
50. Pow(x, n)
xn = {
(x2)(n/2) // n为偶数
x * (x2)(n/2)// n为奇数
}
var myPow = function(x, n) {
if (n === 0) return 1
// n 为负数
if (n < 0) {
return 1 / myPow(x, -n)
}
// n 为奇数
if (n % 2) {
return x * myPow(x, n - 1)
}
// n 为偶数
return myPow(x * x, n / 2)
};
875.爱吃香蕉的珂珂0.3k
var minEatingSpeed = function(piles, h) {
let left = 1
let right = Math.max(...piles)
const canFinished = (piles, H, speed) => {
let time = 0
for (let item of piles) {
time += Math.ceil(item / speed)
}
return time <= H
}
while (left <= right) {
let mid = Math.floor((left + right) / 2)
if (canFinished(piles, h, mid)) {
right = mid - 1
} else {
left = mid + 1
}
}
return left
};
1011.在 D 天内送达包裹的能力
var shipWithinDays = function(weights, days) {
let left = Math.max(...weights) // 最小载重必须能载一个包裹，故取最大重量包裹
let right = weights.reduce((a, b) => a + b) // 最大载重就是一天内运完所有包裹
const canFinish = (weights, DAY, cap) => {
let current = 0
let day = 1
for (let w of weights) {
current += w
// 超过每天的限制, 这个货就放在下一天运
if (current > cap) {
current = w
day ++
}
}
return day <= DAY
}
while (left <= right) {
let mid = Math.floor((left + right) / 2)
if (canFinish(weights, days, mid)) {
right = mid - 1
} else {
left = mid + 1
}
}
return left
};
twoSum 问题
1.两数之和
- 有序：
前后指针 - 无序：
hash表
哈希表存已遍历的值和下标，若在哈希表已存在说明当前值和已遍历的某一值加起来刚好为target值
var twoSum = function(nums, target) {
let hash = {}
for (let i = 0; i < nums.length; i ++) {
const x = target - nums[i]
if (hash[x] || hash[x] === 0) {
return [i, hash[x]]
} else {
hash[nums[i]] = i
}
}
};
若有收获，就点个赞吧
0 人点赞
