滑动窗口(Sliding Window)是一种常用的算法技巧,用于处理数组或字符串相关
的问题。
它通过维护一个固定大小的窗口来解决问题。
具体来说,滑动窗口算法通常包含以下步骤:
1. 先进行右侧指针(窗口)移动位置(后移)
2. 判断是否符合预期。
1. 符合,进行其他处理,比如reurn等
2. 不符合,判断左侧指针是否移动位置
1. 移动或着不移动
3. 进入下一次循环
滑动窗口算法的优势在于其时间复杂度通常为O(n),其中n为数组或字符串的长度。这使得滑动窗口算法在处理大规模数据时非常高效。
滑动窗口算法可以应用于许多问题,如:
它的核心思想是通过调整窗口的起始位置和结束位置
来寻找最优解
。
当使用JavaScript来实现滑动窗口算法时,我们可以举一个经典的例子:
在一个数组中查找连续子数组的最大值之和。
下面是使用JavaScript实现滑动窗口算法求解最大子数组和的示例代码:
function maxSubarraySum(nums, k) {
let windowSum = 0;
for (let i = 0; i < k; i++) {
windowSum += nums[i]; // 计算初始窗口的和
}
let maxSum = windowSum; // 初始化最大和为窗口的初始和
for (let i = k; i < nums.length; i++) {
windowSum = windowSum + nums[i] - nums[i - k]; // 移动窗口,更新窗口的和
maxSum = Math.max(maxSum, windowSum); // 更新最大和
}
return maxSum;
}
// 示例输入
let nums = [1, -3, 2, 4, -1, 5, -2, 3];
let k = 3;
// 调用函数求解最大子数组和
let result = maxSubarraySum(nums, k);
console.log("最大子数组和:", result);
在这个例子中,我们定义了一个maxSubarraySum
函数,该函数接受一个数组nums
和一个整数k
作为参数,用于求解数组中长度为k的连续子数组的最大和。通过维护一个长度为k的窗口,不断调整窗口的位置来求解最大子数组和。
通过这个示例,你可以看到如何使用JavaScript实现滑动窗口算法来解决问题。滑动窗口算法在实际应用中非常常见,能够高效地处理数组和字符串相关的问题。
地址:https://leetcode.cn/problems/longest-substring-without-repeating-characters/
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
提示:
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
解答
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
// 思路:
// 1. 先进行右侧指针(窗口)移动位置(后移)
// 2. 判断是否符合预期。
// 2.1 符合,进行其他处理,比如reurn等
// 2.2 不符合,左侧指针是否移动位置
// 2.2.1 移动或着不移动
// 3. 进入下一次循环
if(s.length <=1){
return s.length
}
//定义指针
let left = 0
let right = 1
// 定义无重复最长字串
let max = 0
// 定义字串
let temp
// 当且仅当右侧指针向右侧移动不超过s
while(right < s.length){
temp = s.slice(left,right) // splice(0,1)
// 判断当前元素是否包含right所在位置下表元素
if(temp.indexOf(s.charAt(right)) > -1){
left ++
continue
} else {
right ++
}
if(right - left > max){
max = right - left
}
}
return max
};