双指针常用模板
板子大概如下
// 首先for循环枚举**右端点i**
for(let i = 0, j = 0, check = 0; i < n; i++){
// 先更新当前值,比如count += arr[i]、sum *= arr[i]...
updateCurrent()
// 开始移动左端点,并保证while里的条件是符合答案要求的,比如大于等于target或者严格小于target
while(currentIsInvalid){
checkCurrent()
j++
}
// 缩减完了的window,需要再次检查是否满足答案要求,如满足,则更新答案
updateRes()
}
return res
var minWindow = function(s, t) {
// 使用两个hash表,一个是记录t字串里字符出现的数量,另一个记录窗口[start, end]里面出现的有效字符数量
// 有效字符表示,当前加入窗口的字符,对满足t里面的字符个数有贡献,而不是冗余的个数
const cnt = {}
for(let i = 0; i < t.length; i++){
cnt[t[i]] = (cnt[t[i]] || 0) + 1
}
const window = {}
let res = ''
let valid = 0
for(let start = 0, end = 0; end < s.length; end++){
// 加入窗口
window[s[end]] = (window[s[end]] || 0) + 1
// 判断当前加入的字符是否为有效字符
if(window[s[end]] <= cnt[s[end]]) valid++
// 开始向右移动start, 由于s[start]有可能是t里面没有出现过的字符,在js里会变成undefined,所以需要兜底转为0
while(window[s[start]] > (cnt[s[start]] || 0)) {
window[s[start]]--
start++
}
// 如果此时是比res更小的值,则记录substring
if(valid === t.length){
if(!res || end - start + 1 < res.length){
res = s.substring(start, end + 1)
}
}
}
return res
};
var minSubArrayLen = function(target, nums) {
const n = nums.length
let res = Infinity
for(let i = 0, j = 0, total = 0; i < n; i++){
total += nums[i]
while(total - nums[j] >= target) {
total -= nums[j]
j++
}
if(total >= target) {
res = Math.min(res, i - j + 1)
}
}
return res === Infinity ? 0 : res
};
var numSubarrayProductLessThanK = function(nums, k) {
if(k <= 1) return 0
let res = 0
let product = 1
for(let i = 0, j = 0; i < nums.length; i++){
product *= nums[i]
while(product >= k){
product /= nums[j]
j++
}
if(product < k){
res += i - j + 1
}
}
return res
};
var lengthOfLongestSubstring = function(s) {
const count = {}
let res = 0
for(let i = 0, j = 0; i < s.length; i++){
count[s[i]] = (count[s[i]] || 0) + 1
while(count[s[i]] > 1){
count[s[j]]--
j++
}
if(count[s[i]]){
res = Math.max(res, i - j + 1)
}
}
return res
};
var longestOnes = function(nums, k) {
let res = 0
for(let i = 0, j = 0, count = 0; i < nums.length; i++){
count += nums[i] === 0
while(count > k){
count -= nums[j] === 0
j++
}
res = Math.max(res, i - j + 1)
}
return res
};
var balancedString = function(s) {
const count = {
'Q': 0,
'W': 0,
'E': 0,
'R': 0
}
const n = s.length
const target = n / 4
// 先统计一边整个字符的状况
for(let i = 0; i < n; i++){
count[s[i]]++
}
// 如果已经都刚好满足,则直接return 0
if(count['Q'] === target && count['W'] === target && count['E'] === target && count['R'] === target) return 0
let res = n
for(let i = 0, j = 0; i < n; i++){
count[s[i]]--
// 只有当除窗口外其余的字符(Q/W/E/R)个数都 <= n/4,才能通过替换窗口里的字符来达到平衡
while(count['Q'] <= target && count['W'] <= target && count['E'] <= target && count['R'] <= target){
res = Math.min(res, i - j + 1)
count[s[j]]++
j++
}
}
return res
};
var minOperations = function(nums, x) {
let total = 0
for(const num of nums){
total += num
}
// 是否存在一个window使得,total - windowSum === x =转化为=> 是否存在一个 window === total - x
// 操作数为 n - 1 - i + j
let res = Infinity
const target = total - x
const n = nums.length
for(let i = 0, j = 0, window = 0; i < n; i++){
window += nums[i]
while(j <= i && window > target){
window -= nums[j]
j++
}
if(window === target){
res = Math.min(res, n - 1 - i + j)
}
}
return res === Infinity ? -1 : res
};
var countSubarrays = function(nums, k) {
const max = Math.max(...nums)
let res = 0
for(let i = 0, j = 0, count = 0; i < nums.length; i++){
if(nums[i] === max) count += 1
while(count >= k){
if(nums[j] === max) count -= 1
j++
}
res += j
}
return res
};
LC 159. 至多包含两个不同字符的最长子串
LC 340. 至多包含 K 个不同字符的最长子串
这两题基本一样,把k换成2即可
var lengthOfLongestSubstringKDistinct = function(s, k) {
const n = s.length
let res = 0
const cnt = new Map()
for(let i = 0, j = 0; i < n; i++){
cnt.set(s[i], (cnt.get(s[i]) || 0) + 1) // 加入字符
while(cnt.size > k){ // 超过窗口
cnt.set(s[j], (cnt.get(s[j]) || 0) - 1) // 减去窗口队头cnt
if(cnt.get(s[j]) <= 0) cnt.delete(s[j]) // 如果没了则删掉它
j++
}
res = Math.max(res, i - j + 1)
}
return res
};