Julian's Blog

Keep Going

0%

力扣top100-滑动窗口

Posted on In Disqus: Valine:
Symbols count in article: 2.2k Reading time ≈ 2 mins.

滑动窗口

3.无重复字符的最长子串

3.无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

哈希表+滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) {
            return 0;
        }
        Map<Character, Integer> map = new HashMap<>();
        int left = 0, max = 0;
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                //从重复的字符的下一个字符重新开始
                left = Math.max(left, map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i), i);
            max = Math.max(max, i - left + 1);
        }
        return max;
    }
}

438.找到字符串中所有字母异位词

438.找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

1
2
3
4
5
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
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
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        //数组统计各个字母的数量
        int[] num = new int[26];
        for (int i = 0; i < p.length(); i++) {
            num[p.charAt(i) - 'a']++;
        }
        //滑动窗口左指针
        int l = 0;
        for (int r = 0; r < s.length(); r++) {
            //更新当前窗口内的字符数量
            num[s.charAt(r) - 'a']--;
            //当有p中不存在的字母或者是重复的字母出现就会进入循环
            //滑动窗口左指针向右移动，若遇见重复的字符 l = r ；若是遇见p中不存在的字符，r比l大1，这样刚好可以过掉那个p中不存在的字符
            while (num[s.charAt(r) - 'a'] < 0) {
                num[s.charAt(l) - 'a']++;   //恢复计数的数组
                l++;
            }
            if (r - l + 1 == p.length()) {
                ans.add(l);
            }
        }
        return ans;
    }
}

550.和为K的子数组

550.和为K的子数组

利用前缀和还有哈希表。

1
2
3
4
5
6
假设数组的前缀和数组为prefixSum，其中prefixSum[i]表示从数组起始位置到第i个位置的元素之和。那么对于任意的两个下标i和j（i < j），如果prefixSum[j] - prefixSum[i] = k，即从第i个位置到第j个位置的元素之和等于k，那么说明从第i+1个位置到第j个位置的连续子数组的和为k。

通过遍历数组，计算每个位置的前缀和，并使用一个哈希表来存储每个前缀和出现的次数。在遍历的过程中，我们检查是否存在prefixSum[j] - k的前缀和，如果存在，说明从某个位置到当前位置的连续子数组的和为k，我们将对应的次数累加到结果中。
    
由于pre[i]的计算只与前一项的答案有关，因此我们可以不用建立 pre数组，直接用 pre变量来记录 pre[i−1]的答案即可。
提前设置(0,1)是因为我们是如果相减结果是0的话，就说明当前位置前缀和就等于k，但是由于代码的put是在count之后的，所以提前先把(0,1)设置好，不会影响结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int subarraySum(int[] nums, int k) {
        int ans = 0, pre = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];
            if (map.containsKey(pre - k)) {
                ans += map.get(pre - k);
            }
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }
        return ans;
    }
}