一个月速刷leetcodeHOT100 day06 一道滑动窗口 两道普通数组

最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组
是数组中的一个连续部分。
示例 1：
**输入：**nums = [-2,1,-3,4,-1,2,1,-5,4]
**输出：**6
**解释：**连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
**输入：**nums = [1]
**输出：**1
示例 3：
**输入：**nums = [5,4,-1,7,8]
**输出：**23

function maxSubarraySum(nums) {

if(nums.length === 1) return nums[0]

let maxSum = nums[0]; // 定义一个变量 maxSum 来存储当前最大子序和，初始值设为数组的第一个元素值。

let currentSum = nums[0]; // 定义一个变量 currentSum 来存储当前的子序和，初始值也为数组的第一个元素值。

for (let i = 1; i < nums.length; i++) { // 从数组的第二个元素开始遍历

currentSum = Math.max(nums[i], currentSum + nums[i]); // 计算当前元素值与当前元素值加上 currentSum 的较大值，更新 currentSum。

maxSum = Math.max(maxSum, currentSum); // 比较 currentSum 与 maxSum，取较大值更新 maxSum。

}

return maxSum; // 遍历完整个数组后，maxSum 即为最大子序和。

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
思路:当我们需要合并区间时，我们可以遍历给定的区间数组，并通过比较相邻的区间来判断它们是否有重叠。
如果存在重叠，我们将这两个区间合并成一个新的区间，并继续进行下一轮的比较；如果不存在重叠，我们将当前区间加入结果数组，并继续处理下一个区间。
新区间的起始位置为当前区间的起始位置，结束位置为两个区间结束位置的较大值。
合并后的区间放入下一个位置

var merge = function(intervals) {

let len = intervals.length;

let res = [];

intervals.sort((a, b) => a[0] - b[0]); // 先按照起始位置排序

let i = 0;

while (i < len) {

let currInterval = intervals[i];

let j = i + 1;

while (j < len && intervals[j][0] <= currInterval[1]) {

currInterval[1] = Math.max(currInterval[1], intervals[j][1]); // 更新结束位置

j++;

}

res.push(currInterval);

i = j;

}

return res;

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长
子串,
的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
思路:我们可以使用滑动窗口来解释, 我们可以维护一个滑动窗口，其中包含的字符都是唯一的。
随着我们遍历输入字符串，我们不断调整滑动窗口的起始位置和结束位置，以确保窗口中的字符都是唯一的。

var lengthOfLongestSubstring = function(s) {
if (s.length === 0) {
return 0;
}
let maxLength = 0;
let start = 0;
let end = 0;
let charSet = new Set();
while (end < s.length) {
if (!charSet.has(s[end])) {
charSet.add(s[end]);
maxLength = Math.max(maxLength, end - start + 1);
end++;
} else {
charSet.delete(s[start]);
start++;
}
}
return maxLength;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20