先来回顾一下上期的问题及答案:
「最大子序和」(Maximum Subarray)。
题目描述: 给定一个整数数组 nums
,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
解题思路:
使用动态规划的思想解决问题。
定义两个变量
maxSum
和currSum
,分别表示最大和和当前连续子数组的和,初始化为数组的第一个元素。遍历数组,对于每个元素,计算当前元素加入之后的连续子数组的和,与当前元素自身进行比较,取较大的值作为新的
currSum
。同时,更新
maxSum
,记录最大的和。最终返回
maxSum
。
时间复杂度分析:
遍历整个数组的时间复杂度为 O(n),其中 n 是数组的长度。
空间复杂度分析:
只使用了常量级别的额外空间,所以空间复杂度为 O(1)。
例如:
console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6
console.log(maxSubArray([1])); // 1
console.log(maxSubArray([5, 4, -1, 7, 8])); // 23
代码实现:
function maxSubArray(nums) {let maxSum = nums[0];let currSum = nums[0];for (let i = 1; i < nums.length; i++) {currSum = Math.max(nums[i], currSum + nums[i]);maxSum = Math.max(maxSum, currSum);}return maxSum;
}
在上述例子中,给定数组分别为 [-2, 1, -3, 4, -1, 2, 1, -5, 4]
、[1]
和 [5, 4, -1, 7, 8]
。通过调用 maxSubArray
函数找到具有最大和的连续子数组。最大和分别为 6
、1
和 23
。
2023年6月6日
「无重复字符的最长子串」(Longest Substring Without Repeating Characters)
题目描述: 给定一个字符串 s,请找出其中不含有重复字符的最长子串的长度。 解题思路:
使用滑动窗口的思想解决问题。
定义两个指针 start 和 i,分别表示子串的起始位置和结束位置。
遍历字符串 s,对于每个字符,判断其是否在当前子串中出现过。
如果字符已经出现过,则更新 start 为该字符上次出现的位置的下一个位置。
更新 maxLength,记录最长的不重复子串的长度。
最终返回 maxLength。
上面问题的答案会在第二天的公众号推文中公布,大家可以关注公众号:程序员每日三问,第一时间获得推送内容。
学习不打烊,充电加油只为遇到更好的自己,每天早上9点纯手工发布面试题(死磕自己,愉悦大家) 希望大家在这浮夸的程序员圈里保持冷静,每天坚持花20分钟来学习与思考,在千变万化,类库层出不穷的今天,不要等到找工作时才狂刷题,提倡每日学习。