Problem: 438. 找到字符串中所有字母异位词
思路
👩🏫 参考题解
滑动窗口 + 数组
⏰ 时间复杂度:
O
(
n
)
O(n)
O(n)
🌎 空间复杂度:
O
(
1
)
O(1)
O(1)文章来源地址https://www.toymoban.com/news/detail-821994.html
class Solution {
// 滑动窗口 + 数组
public List<Integer> findAnagrams(String s, String p)
{
int n = s.length();
int m = p.length();
List<Integer> ans = new ArrayList<>();
if (n < m)
return ans;
int[] pp = new int[26];
int[] ss = new int[26];
for (int i = 0; i < m; i++)
{
pp[p.charAt(i) - 'a']++;
ss[s.charAt(i) - 'a']++;
}
if (Arrays.equals(pp, ss))
ans.add(0);
for (int i = m; i < n; i++)
{
ss[s.charAt(i - m) - 'a']--;
ss[s.charAt(i) - 'a']++;
if (Arrays.equals(ss, pp))
ans.add(i - m + 1);
}
return ans;
}
}
滑动窗口 + 双指针
文章来源:https://www.toymoban.com/news/detail-821994.html
⏰ 时间复杂度:
O
(
n
)
O(n)
O(n)
🌎 空间复杂度:
O
(
1
)
O(1)
O(1)
class Solution {
public List<Integer> findAnagrams(String s, String p)
{
int n = s.length();
int m = p.length();
List<Integer> ans = new ArrayList<>();
if (n < m)
return ans;
int[] pp = new int[26];// 目标串的字符数
int[] win = new int[26];// 当前窗口拥有的字符数
for (int i = 0; i < m; i++)
pp[p.charAt(i) - 'a']++;
int l = 0;
for (int r = 0; r < n; r++)
{
int rightIdx = s.charAt(r) - 'a';
win[rightIdx]++;
// 加入r字符导致 当前窗口字符个数超出范围,只能移除左边的字符
while (win[rightIdx] > pp[rightIdx])
{
int leftIdx = s.charAt(l) - 'a';
win[leftIdx]--;
l++;
}
// 注意:走到这,只有 当前窗口内字符数不够 这种情况,上边的while循环保证了当前的窗口的每个字符肯定 <= 目标数
if (r - l + 1 == m)// 只要当前窗口大小 == 目标串长度
ans.add(l);
}
return ans;
}
}
到了这里,关于力扣hot100 找到字符串中所有字母异位词 滑动窗口 双指针 一题双解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!