無重復字符的最長字串(003)
先看代碼
class Solution {
public int lengthOfLongestSubstring(String s) {
int res = 0;
int lef = 0;
int rig = 0;
int[] memo = new int[128];
while (rig < s.length()){
char clef = s.charAt(lef);
char crig = s.charAt(rig);
if (memo[crig] > 0){
memo[clef]--;
lef++;
continue;
}
memo[crig]++;
res = Math.max(res, rig - lef + 1);
rig++;
}
return res;
}
}
- 分析
根據題目條件<無重復>
通過lef和rig 維護一個滑動窗口, memo來記錄遇到字符的次數
rig一直向右擴張, 當出現數字重復, 移動lef 收縮窗口
- 感悟
尋找連續區間就讓人很自然而然想到滑動窗口
每次窗口移動只用考慮(入窗口, 出窗口)的元素對窗口整體的影響
找到字符串中所有的字母異位詞(438)
先看代碼
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
int lef = 0;
int rig = 0;
int[] memo = new int[26];
for (char c : p.toCharArray()){
memo[c - 'a']++;
}
while(rig < s.length()){
int idx = s.charAt(rig) - 'a';
memo[idx]--;
while(memo[idx] < 0){
memo[s.charAt(lef) - 'a']++;
lef++;
}
if (rig - lef + 1 == p.length()) res.add(lef);
rig++;
}
return res;
}
}
- 分析
和無重復字符的最長字串基本一致, 擴張收縮窗口, 達到條件添加到res
- 感悟
暫無
浙公網安備 33010602011771號