leetcode 438 Find All Anagrams in a String


  1. Find All Anagrams in a String:题目链接

方法1:双指针之滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.ArrayList;
import java.util.List;

public class Solution1 {
// 时间复杂度O(N)
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
int left = 0, right = 0; // [left, right) 滑动窗口
int[] hash = new int[128]; // 声明哈希表 128:ASCII 256:扩展的ASCII
// hash中存放p中字符出现的次数
for (int i = 0; i<p.length();++i) {
hash[p.charAt(i)]++;
}

int count = 0; // 计数器
while (right < s.length()) {
// 每次都将当前遍历的元素次数-1 ,那么不属于p里面的字符 出现的频率肯定是负数
// 当发现当前元素频率大于等于1 说明当前元素是p中的某一个 计数器++
if (hash[s.charAt(right++)]-- >= 1) {
count++;
}
// 如果计数器等于p的长度 说明找到了符合条件的答案
if (count == p.length()){
res.add(left);
}
// 如果发现left所在位置元素的频率>=0 说明是p中的某个元素 (不是p中的元素在第一个if时 频率已经是复述了)
if (right -left == p.length() && hash[s.charAt(left++)]++ >= 0){
count--;
}
}
return res;
}

public static void main(String[] args) {
String s = "cbaebabacd";
String p = "abc";
System.out.println(new Solution1().findAnagrams(s, p));
}
}

另外一种用map的方法,但是效率不知道为什么非常低

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.*;

public class Solution2 {

public List<Integer> findAnagrams(String s, String p) {
List<Integer> list = new ArrayList<>();
Map<Character, Integer> ms = new HashMap<>();
Map<Character, Integer> mp = new HashMap<>();
Vector v = new Vector();
for (int i =0; i<p.length();++i) {
mp.put(p.charAt(i), mp.getOrDefault(p.charAt(i), 0) + 1);
}

int left = 0, right = 0;
while (right < s.length()){
ms.put(s.charAt(right), ms.getOrDefault(s.charAt(right), 0) + 1);
right++;
if (right - left == p.length()){
if (ms.equals(mp)) {
list.add(left);
}
char ch = s.charAt(left);
if (ms.get(ch) > 1){
ms.put(ch, ms.get(ch)-1);
}else{
ms.remove(ch);
}
left++;
}
}
return list;
}

public static void main(String[] args) {
String s = "cbaebabacd";
String p = "abc";
System.out.println(new Solution2().findAnagrams(s, p));
}
}

pS: 源代码链接

文章目录
  1. 1. 方法1:双指针之滑动窗口
|