学习记录：js算法（二十）：子数组最大平均数 I、无重复字符的最长子串
文章目录
- 子数组最大平均数 I
- 我的思路
- 网上思路
- 无重复字符的最长子串
- 我的思路
- 网上思路
- 总结
子数组最大平均数 I
给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
任何误差小于 10-5 的答案都将被视为正确答案。
示例 1：
输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
示例 2：
输入：nums = [5], k = 1
输出：5.00000
我的思路
循环
网上思路
滑动窗口
我的思路
var findMaxAverage = function (nums, k) {
let maxAverage = -Infinity;
const n = nums.length;
for (let i = 0; i <= n - k; i++) {
let currentSum = 0;
for (let j = i; j < i + k; j++) {
currentSum += nums[j];
}
const currentAverage = currentSum / k;
maxAverage = Math.max(maxAverage, currentAverage);
}
return maxAverage;
}
讲解
首先初始化 maxAverage 为负无穷，这样任何计算的平均数都能更新它。
然后循环：
- 外层循环 从 0 到 n - k ，用于确定每个子数组的起始位置。
- 内层循环 从 i 到 i + k ，用于计算当前子数组的和，将当前子数组的元素逐一相加，得到 currentSum 。
通过 currentSum / k 计算当前子数组的平均数。
使用 Math.max 更新 maxAverage，确保它始终保持最大的平均值。
网上思路
var findMaxAverage = function (nums, k) {
// 计算前 k 个元素的和
let currentSum = 0;
for (let i = 0; i < k; i++) {
currentSum += nums[i];
}
let maxSum = currentSum;
// 滑动窗口
for (let i = k; i < nums.length; i++) {
currentSum += nums[i] - nums[i - k]; // 更新窗口和
maxSum = Math.max(maxSum, currentSum); // 更新最大和
}
// 计算最大平均数
return maxSum / k;
}
讲解
- 初始窗口和计算：
我们首先计算数组的前 k 个元素的和，这样我们就有了一个初始的窗口和。
例如，对于数组 nums = [1, 12, -5, -6, 50, 3] 和 k=4 ，我们计算前 4 个元素的和：1 + 12 - 5 - 6 = 2。- 滑动窗口：
从第 k 个元素开始，我们逐步向右滑动窗口。每次滑动时，我们需要更新当前窗口的和：
- 移除最左边的元素：当窗口向右滑动时，最左边的元素会被移出窗口。
- 移除最左边的元素：当窗口向右滑动时，最左边的元素会被移出窗口。
这可以通过 currentSum += nums[i] - nums[i - k] 来实现。这里 nums[i] 是新加入的元素，而 nums[i - k] 是被移除的元素。- 更新最大和：
在每一步中，我们将当前窗口的和与之前记录的最大和进行比较。如果当前和更大，就更新最大和。
例如，在第二次滑动时，我们可能会计算新的窗口和 12 - 5 - 6 + 50 = 51，然后更新最大和。- 计算平均数：
一旦我们遍历完所有可能的窗口，最大和就被记录下来了。最后，我们只需将这个最大和除以
k 就能得到最大平均数。
无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
我的思路
循环
网上思路
滑动窗口
我的思路
var lengthOfLongestSubstring = function (s) {
let maxLength = 0;
for (let i = 0; i < s.length; i++) {
let charSet = new Set();
let currentLength = 0;
for (let j = i; j < s.length; j++) {
if (charSet.has(s[j])) {
break;
}
charSet.add(s[j]);
currentLength++;
}
maxLength = Math.max(maxLength, currentLength);
}
return maxLength;
};
讲解
maxLength 用于记录最长子串的长度。
外层循环 从 0 到 s.length - 1，用于确定每个子串的起始位置。
内层循环从当前的起始位置 i 开始，逐个检查字符。
- 使用一个集合 charSet 来存储当前子串中的字符。
- 如果当前字符 s[j] 已经在集合中，表示有重复字符，使用 break 语句退出内层循环。
- 如果没有重复字符，将当前字符添加到集合，并增加 currentLength。
在内层循环结束后，使用 Math.max 更新 maxLength。
最后返回 maxLength。
网上思路
var lengthOfLongestSubstring = function (s) {
let left = 0; // 左指针
let maxLength = 0; // 最长子串的长度
const charSet = new Set(); // 用于存储当前窗口中的字符
for (let right = 0; right < s.length; right++) {
// 如果字符重复，移动左指针，直到没有重复字符
while (charSet.has(s[right])) {
charSet.delete(s[left]);
left++;
}
// 添加当前字符到集合
charSet.add(s[right]);
// 更新最长子串的长度
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength; // 返回最长子串的长度
};
讲解
- 初始化：
left 指针从 0 开始，maxLength 初始化为 0，集合 charSet 用于存储当前窗口的字符。- 滑动窗口：
right 指针遍历字符串的每个字符。
如果当前字符 s[right] 已经在集合中，表示有重复字符，进入内层 while 循环，移动 left 指针并从集合中删除字符，直到没有重复字符。- 更新集合和长度：
将当前字符添加到集合中。
更新 maxLength 为当前窗口的长度 right - left + 1。- 返回结果：
最后返回 maxLength，即不含重复字符的最长子串的长度。
总结
第一次遇见滑动窗口这一说法，虽然不是很难理解，但是用循环不香吗？