力扣hot100 找到字符串中所有字母异位词 滑动窗口 双指针 一题双解

这篇具有很好参考价值的文章主要介绍了力扣hot100 找到字符串中所有字母异位词 滑动窗口 双指针 一题双解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Problem: 438. 找到字符串中所有字母异位词
力扣hot100 找到字符串中所有字母异位词 滑动窗口 双指针 一题双解,力扣 hot100,leetcode,算法,职场和发展

思路

👩‍🏫 参考题解

滑动窗口 + 数组

力扣hot100 找到字符串中所有字母异位词 滑动窗口 双指针 一题双解,力扣 hot100,leetcode,算法,职场和发展

⏰ 时间复杂度: 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;
	}
}

滑动窗口 + 双指针

力扣hot100 找到字符串中所有字母异位词 滑动窗口 双指针 一题双解,力扣 hot100,leetcode,算法,职场和发展

⏰ 时间复杂度: 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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包