無重復字符的最長字串(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

• 感悟

暫無