此刻
欢迎来到我的博客
访问我的GitHub
238. 除自身以外数组的乘积
238. 除自身以外数组的乘积
通过两次遍历(左到右和右到左)分别计算每个位置左边和右边的乘积,最后将两部分相乘得到结果,避免使用除法且实现O(n)的时间复杂度。
189. 轮转数组
189. 轮转数组
通过三次翻转(整体翻转、前k个元素翻转、剩余元素翻转)实现数组右移k位,时间复杂度O(n),空间复杂度O(1)。
56. 合并区间
56. 合并区间
先按区间起点排序,然后遍历区间进行合并,如果当前区间起点大于上一个区间终点则无法合并(加入新区间),否则合并区间(更新终点为较大值)。
53. 最大子数组和
53. 最大子数组和
遍历数组并累加当前元素,当子数组和小于等于0时舍弃当前子数组重新开始计算,期间不断更新最大和,最终得到全局最大子数组和。
76. 最小覆盖子串
76. 最小覆盖子串
本题使用滑动窗口方法,通过左右指针动态调整窗口大小,配合哈希表统计字符频次,在 O(n) 时间复杂度内找到包含目标字符串所有字符的最小子串。
560. 和为 K 的子数组
560. 和为 K 的子数组
本题使用前缀和 + 哈希表的方法求解。通过构建前缀和数组,可以快速计算任意区间的和。使用哈希表记录每个前缀和出现的次数,当遍历到前缀和s[i]时,查找s[i]-k是否存在于哈希表中,若存在,则找到了和为k的子数组。该方法的时间复杂度为O(n),空间复杂度为O(n)。
3. 无重复字符的最长子串
3. 无重复字符的最长子串
该题使用滑动窗口方法,维护一个无重复字符的窗口。通过左右指针和哈希表,右指针扩展窗口,遇到重复时左指针右移,并持续更新最大长度。此方法的时间复杂度为O(n)。
438. 找到字符串中所有字母异位词
438. 找到字符串中所有字母异位词
本题使用滑动窗口算法,通过维护一个固定大小的窗口和两个哈希表来比较字符频次,从而在O(n)时间复杂度内找出所有异位词的起始位置。