赞
踩
目录
给定一个含有 n
个正整数的数组和一个正整数 target
。
找出该数组中满足其总和大于等于 target
的长度最小的 子数组
并返回其长度。如果不存在符合条件的子数组,返回 0
。
解题思路
- 滑动窗口:使用滑动窗口的方法,通过两个指针
left
和right
来表示窗口的左右边界,用于寻找满足条件的子数组。- 动态调整窗口大小:通过移动
right
指针扩展窗口,直到窗口内的元素和大于或等于目标值target
,然后移动left
指针收缩窗口,以便找到满足条件的最短子数组。- 最小长度:在每次窗口满足条件时,更新最小子数组长度。
步骤说明
初始化:
- 变量
n
用来保存数组nums
的长度。- 变量
sum
用来保存当前窗口内的元素和。- 变量
len
用来保存满足条件的最短子数组的长度,初始值为INT_MAX
表示无穷大。- 两个指针
left
和right
都初始化为 0,表示窗口的左右边界。遍历数组:
- 使用
for
循环遍历数组,right
指针从 0 到n-1
。- 每次将当前元素
nums[right]
加到sum
中,扩展窗口的右边界。收缩窗口:
- 使用
while
循环检查当前窗口内的元素和sum
是否大于或等于目标值target
。- 如果满足条件,更新最短子数组长度
len
为当前窗口长度right - left + 1
和之前的最小长度之间的较小值。- 将窗口左边界元素
nums[left]
从sum
中减去,并将left
指针右移,收缩窗口的左边界。返回结果:
- 如果
len
仍然是INT_MAX
,表示没有找到满足条件的子数组,返回 0。- 否则,返回
len
。
具体代码
class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int n = nums.size(); // 数组长度 int sum = 0; // 当前窗口内元素的总和 int len = INT_MAX; // 记录最短子数组的长度,初始值为最大整数 for (int left = 0, right = 0; right < n; right++) { sum += nums[right]; // 进窗口,更新总和 while (sum >= target) // 如果窗口内总和满足条件,尝试收缩窗口 { len = min(len, right - left + 1); // 更新最短子数组的长度 sum -= nums[left]; // 移动左边界,减少总和 left++; } } return len == INT_MAX ? 0 : len; // 如果未找到满足条件的子数组,返回 0,否则返回最短子数组长度 } };
给定一个字符串 s
,请你找出其中不含有重复字符的 最长子串 的长度。
解题思路
- 滑动窗口:使用滑动窗口的方法,通过两个指针
left
和right
来表示窗口的左右边界,用于寻找最长的无重复字符子串。- 哈希数组:使用哈希数组
hash
记录每个字符在当前窗口内出现的次数。- 动态调整窗口大小:通过移动
right
指针扩展窗口,直到窗口内有重复字符,然后移动left
指针收缩窗口,以便保持窗口内的字符都是唯一的。- 最大长度:在每次窗口内没有重复字符时,更新最长子串的长度。
步骤说明
初始化:
- 变量
hash
用来记录每个字符在当前窗口内出现的次数,大小为128(因为ASCII字符一共128个)。- 变量
left
和right
初始化为 0,表示窗口的左右边界。- 变量
n
用来保存字符串s
的长度。- 变量
ret
用来保存最长无重复字符子串的长度,初始值为 0。遍历字符串:
- 使用
while
循环遍历字符串,当right
小于n
时进行循环。- 每次将当前字符
s[right]
在hash
中的值加1,扩展窗口的右边界。收缩窗口:
- 使用
while
循环检查当前窗口内的字符s[right]
是否出现多次。- 如果出现多次,则将窗口左边界字符
s[left]
在hash
中的值减1,并将left
指针右移,收缩窗口的左边界,直到窗口内字符都是唯一的。更新最大长度:
- 在每次窗口内字符都是唯一时,更新最长子串的长度
ret
为当前窗口长度right - left + 1
和之前的最大长度之间的较大值。返回结果:
- 返回
ret
,即最长无重复字符子串的长度。
具体代码
class Solution { public: int lengthOfLongestSubstring(string s) { int hash[128] = { 0 }; // 记录字符的频次 int left = 0, right = 0, n = s.size(); // 初始化左右边界和字符串长度 int ret = 0; // 记录最长子字符串的长度 while (right < n) { hash[s[right]]++; // 进窗口,更新当前字符的频次 while (hash[s[right]] > 1) // 如果窗口内有重复字符,收缩窗口 hash[s[left++]]--; // 移动左边界,并更新频次 ret = max(ret, right - left + 1); // 更新结果 right++; // 移动右边界 } return ret; // 返回最长不包含重复字符的子字符串长度 } };
给定一个二进制数组 nums
和一个整数 k
,如果可以翻转最多 k
个 0
,则返回 数组中连续 1
的最大个数 。
解题思路
- 滑动窗口:使用滑动窗口的方法,通过两个指针
left
和right
来表示窗口的左右边界,用于寻找包含最多k
个 0 的最长连续子数组。- 计数器:使用变量
zero
记录当前窗口内 0 的数量。- 动态调整窗口大小:通过移动
right
指针扩展窗口,直到窗口内的 0 的数量超过k
,然后移动left
指针收缩窗口,以便保持窗口内的 0 的数量不超过k
。- 最大长度:在每次窗口内的 0 的数量不超过
k
时,更新最长子数组的长度。
步骤说明
初始化:
- 变量
ret
用来保存包含最多k
个 0 的最长连续子数组的长度,初始值为 0。- 变量
left
和right
初始化为 0,表示窗口的左右边界。- 变量
zero
用来记录当前窗口内 0 的数量,初始值为 0。遍历数组:
- 使用
for
循环遍历数组,right
指针从 0 到nums.size()-1
。- 每次将当前元素
nums[right]
加到窗口中,如果是 0,则zero
加1。收缩窗口:
- 使用
while
循环检查当前窗口内的 0 的数量zero
是否超过k
。- 如果超过
k
,则将窗口左边界元素nums[left]
从窗口中移出,并将left
指针右移,如果移出的元素是 0,则zero
减1。更新最大长度:
- 在每次窗口内的 0 的数量不超过
k
时,更新最长子数组的长度ret
为当前窗口长度right - left + 1
和之前的最大长度之间的较大值。返回结果:
- 返回
ret
,即包含最多k
个 0 的最长连续子数组的长度。
具体代码
class Solution { public: int longestOnes(vector<int>& nums, int k) { int ret = 0; // 记录最长子数组的长度 for(int left = 0, right = 0, zero = 0; right < nums.size(); right++) { if(nums[right] == 0) // 进窗口 zero++; while(zero > k) // 如果窗口中的0数量超过k,收缩窗口 { if(nums[left++] == 0) // 移动左边界 { zero--; } } ret = max(ret, right - left + 1); // 更新结果 } return ret; // 返回结果 } };
给你一个整数数组 nums
和一个整数 x
。每一次操作时,你应当移除数组 nums
最左边或最右边的元素,然后从 x
中减去该元素的值。请注意,需要 修改 数组以供接下来的操作使用。
如果可以将 x
恰好 减到 0
,返回 最小操作数 ;否则,返回 -1
。
解题思路
- 定义变量
sum
计算数组中所有元素的总和,然后定义目标值target
为sum - x
。- 使用滑动窗口的方法找到最长的子数组,其和为
target
。- 最终结果是
nums.size() - ret
,即数组的长度减去最长子数组的长度。
步骤说明
初始化:
- 计算数组
nums
所有元素的总和sum
。- 计算目标值
target
为sum - x
。- 如果
target < 0
,返回 -1,因为不可能找到和为负数的子数组。定义变量:
ret
初始化为 -1,用于存储找到的最长子数组的长度。left
和right
分别为滑动窗口的左右边界,初始化为 0。tmp
为当前滑动窗口内的元素和,初始化为 0。滑动窗口:
- 遍历数组
nums
,right
从 0 到nums.size()
。- 将
nums[right]
加到tmp
中,表示右边界扩展。- 如果
tmp
大于target
,不断将nums[left]
减去tmp
中,并将left
右移,表示左边界收缩。- 如果
tmp
等于target
,更新ret
为当前窗口长度,即right - left + 1
。结果返回:
- 如果
ret
仍然是 -1,返回 -1,表示没有找到满足条件的子数组。- 否则返回
nums.size() - ret
,即操作次数。
具体代码
class Solution { public: int minOperations(vector<int>& nums, int x) { int sum = 0; for(int a : nums) sum += a; // 计算数组的总和 int target = sum - x; // 计算需要找到的子数组和 if(target < 0) return -1; // 如果目标和小于0,返回-1 int ret = -1; // 记录最长子数组长度 for(int left = 0, right = 0, tmp = 0; right < nums.size(); right++) { tmp += nums[right]; // 进窗口,更新当前和 while(tmp > target) // 如果当前和超过目标,收缩窗口 tmp -= nums[left++]; if(tmp == target) // 如果当前和等于目标,更新最长子数组长度 ret = max(ret, right - left + 1); } if(ret == -1) // 如果没有找到符合条件的子数组,返回-1 return ret; else return nums.size() - ret; // 返回移除的元素数量 } };
你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 fruits
表示,其中 fruits[i]
是第 i
棵树上的水果 种类 。
你想要尽可能多地收集水果。然而,农场的主人设定了一些严格的规矩,你必须按照要求采摘水果:
给你一个整数数组 fruits
,返回你可以收集的水果的 最大 数目。
解题思路
目的是在一个数组
f
中找到包含两种不同元素的最长子数组。该问题可以被视为一个“滑动窗口”问题,通过使用滑动窗口的方法保持一个窗口,使得窗口内最多包含两种不同的元素。
步骤说明
初始化:
- 定义一个哈希数组
hash
,用于记录每个元素出现的次数,大小为 100001,初始值都为 0。- 定义变量
ret
,用于记录最长子数组的长度,初始值为 0。- 定义滑动窗口的左右边界
left
和right
,初始值为 0。- 定义变量
kinds
,用于记录窗口内不同元素的种类数,初始值为 0。滑动窗口:
- 遍历数组
f
,右边界right
从 0 到f.size()
:
- 如果
hash[f[right]]
为 0,说明这是一个新种类,kinds
增加 1。- 将当前元素
f[right]
的计数加 1。- 如果
kinds
大于 2,说明窗口内的不同元素超过两种,需要收缩左边界:
- 将
f[left]
的计数减 1。- 如果
hash[f[left]]
为 0,说明这个种类已经完全移出窗口,kinds
减少 1。- 左边界
left
右移。- 更新
ret
为当前窗口的最大长度,即right - left + 1
。返回结果:
- 返回
ret
,即找到的最长子数组的长度。
具体代码
class Solution { public: int totalFruit(vector<int>& f) { int hash[100001] = { 0 }; // 记录每种水果的频次 int ret = 0; // 记录最长子数组的长度 for (int left = 0, right = 0, kinds = 0; right < f.size(); right++) { if (hash[f[right]] == 0) kinds++; // 新出现的水果种类 hash[f[right]]++; while (kinds > 2) // 如果窗口中有超过两个不同种类的水果,收缩左边界 { hash[f[left]]--; if (hash[f[left]] == 0) kinds--; // 如果某种水果完全移除,减少种类计数 left++; } ret = max(ret, right - left + 1); // 更新结果 } return ret; // 返回结果 } };
给定两个字符串 s
和 p
,找到 s
中所有 p
的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。
解题思路
目标是找到字符串
s
中所有与字符串p
具有相同字符的排列(即找出所有的字母异位词)。该问题可以使用滑动窗口的方法来解决。我们使用两个哈希数组分别记录p
的字符频率和当前窗口中字符的频率,然后通过滑动窗口来找到符合条件的子串。
步骤说明
初始化:
hash1
用于记录字符串p
中每个字符的频率。hash2
用于记录当前滑动窗口中每个字符的频率。m
为字符串p
的长度,用于确定窗口大小。ret
用于存储结果,即符合条件的起始位置。初始化
hash1
:
- 遍历字符串
p
,更新hash1
中每个字符的频率。滑动窗口:
right
从 0 到s.size()
遍历字符串s
,扩展窗口右边界。- 更新
hash2
中当前字符的频率,并根据字符频率更新计数器count
。- 如果当前窗口大小超过了
m
,收缩左边界:
- 更新
hash2
中移出字符的频率,并调整count
。- 如果
count
等于m
,说明当前窗口中的字符排列符合要求,将左边界的索引加入结果ret
。返回结果:
- 返回结果
ret
,包含所有符合条件的起始位置。
具体代码
class Solution { public: vector<int> findAnagrams(string s, string p) { vector<int> ret; // 用于存储结果 int hash1[26] = { 0 }; // 记录字符串 p 中每个字符的频率 for (auto ch : p) hash1[ch - 'a']++; // 更新 hash1 int hash2[26] = { 0 }; // 记录当前窗口中每个字符的频率 int m = p.size(); // 字符串 p 的长度 for (int left = 0, right = 0, count = 0; right < s.size(); right++) { char in = s[right]; if (++hash2[in - 'a'] <= hash1[in - 'a']) count++; // 更新字符计数 if (right - left + 1 > m) // 如果当前窗口大小超过 m,收缩窗口 { char out = s[left++]; if (hash2[out - 'a']-- < hash1[out - 'a']) count--; // 更新字符计数 } if (count == m) // 如果计数等于 m,说明窗口中的字符排列符合要求 ret.push_back(left); // 记录结果 } return ret; // 返回结果 } };
给定一个字符串 s
和一个字符串数组 words
。 words
中所有字符串 长度相同。
s
中的 串联子串 是指一个包含 words
中所有字符串以任意顺序排列连接起来的子串。
words = ["ab","cd","ef"]
, 那么 "abcdef"
, "abefcd"
,"cdabef"
, "cdefab"
,"efabcd"
, 和 "efcdab"
都是串联子串。 "acdbef"
不是串联子串,因为他不是任何 words
排列的连接。返回所有串联子串在 s
中的开始索引。你可以以 任意顺序 返回答案。
解题思路
目的是找到字符串
s
中所有包含words
中所有单词的子串的位置,其中每个单词的长度相同,并且每个单词的出现次数也与words
中的出现次数一致。该问题可以使用滑动窗口的方法解决,通过尝试所有可能的起始位置,并维护一个窗口来检查包含的单词是否符合条件。
步骤说明
初始化:
hash1
用于记录words
中每个单词的频次。len
为每个单词的长度。m
为单词的总数。滑动窗口的起始位置:
- 遍历
i
从 0 到len-1
,尝试所有可能的起始位置。维护窗口:
- 定义
hash2
用于记录当前窗口中每个单词的频次。- 初始化左右边界
left
和right
,并设置count
用于记录窗口中符合条件的单词数。- 右边界
right
从i
开始,按单词长度递增,确保窗口内的单词都是长度一致的。进出窗口操作:
- 进窗口:
- 提取当前右边界的单词
in
,更新hash2
中的频次,并根据hash1
更新count
。- 出窗口:
- 如果窗口大小超过
len * m
,移除左边界的单词out
,更新hash2
和count
,并移动左边界。- 更新结果:
- 如果
count
等于m
,说明窗口中包含的单词与words
中的单词完全匹配,记录左边界的索引。返回结果:
- 返回记录的结果
ret
,包含所有符合条件的起始位置。
具体代码
class Solution { public: vector<int> findSubstring(string s, vector<string>& words) { vector<int> ret; // 结果向量 unordered_map<string, int> hash1; // 记录 words 中单词的频次 for (auto& s : words) hash1[s]++; // 初始化 hash1 int len = words[0].size(); // 单词长度 int m = words.size(); // 单词总数 for (int i = 0; i < len; i++) // 尝试所有可能的起始位置 { unordered_map<string, int> hash2; // 记录当前窗口中单词的频次 for (int left = i, right = i, count = 0; right + len <= s.size(); right += len) { // 进窗口 + 维护 count string in = s.substr(right, len); hash2[in]++; if (hash1.count(in) && hash2[in] <= hash1[in]) count++; // 判断 if (right - left + 1 > len * m) { // 出窗口 + 维护 count string out = s.substr(left, len); if (hash1.count(out) && hash2[out] <= hash1[out]) count--; hash2[out]--; left += len; } // 更新结果 if (count == m) ret.push_back(left); // 记录符合条件的起始位置 } } return ret; // 返回结果 } };
给你一个字符串 s
、一个字符串 t
。返回 s
中涵盖 t
所有字符的最小子串。如果 s
中不存在涵盖 t
所有字符的子串,则返回空字符串 ""
。
注意:
t
中重复字符,我们寻找的子字符串中该字符数量必须不少于 t
中该字符数量。s
中存在这样的子串,我们保证它是唯一的答案。
解题思路
目的是找到字符串
s
中包含字符串t
的所有字符(包括重复字符)的最小子串。这个问题可以使用滑动窗口方法来高效解决。通过维护一个窗口来记录当前子串的字符频率,并确保窗口包含t
中的所有字符,最终找到符合条件的最小子串。
步骤说明
初始化:
hash1
用于记录字符串t
中每个字符的频次。kinds
记录t
中有效字符的种类数(即有多少种不同的字符)。hash2
用于记录当前窗口中每个字符的频次。minlen
和begin
用于记录最小子串的长度和起始位置,初始化为无效值。记录
t
中的字符频次:
- 遍历字符串
t
,更新hash1
并记录有效字符的种类数kinds
。滑动窗口:
right
从 0 到s.size()
,遍历字符串s
:
- 将当前右边界的字符加入窗口,更新
hash2
和count
(记录符合条件的字符种类数)。- 判断窗口是否符合条件:
- 当窗口内的字符种类数等于
kinds
时,窗口符合条件。- 更新
minlen
和begin
,记录最小子串的长度和起始位置。- 收缩窗口:
- 移动左边界
left
,更新hash2
和count
,直到窗口不再符合条件。返回结果:
- 根据
begin
和minlen
返回最小子串。如果未找到符合条件的子串,返回空字符串。
具体代码
class Solution { public: string minWindow(string s, string t) { int hash1[128] = { 0 }; // 统计字符串 t 中每个字符的频次 int kinds = 0; // 统计有效字符有多少种 for (auto ch : t) if (hash1[ch]++ == 0) kinds++; // 记录每种字符的频次 int hash2[128] = { 0 }; // 统计窗口内每个字符的频次 int minlen = INT_MAX, begin = -1; // 初始化最小长度和起始位置 for (int left = 0, right = 0, count = 0; right < s.size(); right++) { char in = s[right]; if (++hash2[in] == hash1[in]) count++; // 进窗口 + 维护 count while (count == kinds) // 判断条件 { if (right - left + 1 < minlen) // 更新结果 { minlen = right - left + 1; begin = left; } char out = s[left++]; if (hash2[out]-- == hash1[out]) count--; // 出窗口 + 维护 count } } if (begin == -1) return ""; // 如果没有符合条件的子串,返回空字符串 else return s.substr(begin, minlen); // 返回最小子串 } };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。