3.26

和相等的子数组

https://leetcode.cn/problems/find-subarrays-with-equal-sum/

  • 用哈希表记录两个相邻元素之和，如果哈希表中已经存在，则返回true，否则返回false
  • 时间复杂度O(n)，空间复杂度O(n)，n为nums数组长度
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean findSubarrays(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 1; i < nums.length; i++) {
            boolean add = set.add(nums[i] + nums[i - 1]);
            // 添加失败，说明哈希表中已经存在，返回true
            if (!add) {
                return true;
            }
        }
        return false;
    }
}

3.27

统计只差一个字符的子串数目

https://leetcode.cn/problems/count-substrings-that-differ-by-one-character/

  • 对于 s 中的每一个字符，与 t 中的每一个字符进行比较，如果不同，则分别向左和向右扩展，计算满足条件的子串个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int countSubstrings(String s, String t) {
        int ans = 0;
        int m = s.length(), n = t.length();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (s.charAt(i) != t.charAt(j)) {
                    int l = 0, r = 0;
                    // 向左扩展
                    while (i - l > 0 && j - l > 0 && s.charAt(i - l - 1) == t.charAt(j - l - 1)) {
                        ++l;
                    }
                    // 向右扩展
                    while (i + r + 1 < m && j + r + 1 < n && s.charAt(i + r + 1) == t.charAt(j + r + 1)) {
                        ++r;
                    }
                    // 计算子串个数
                    ans += (l + 1) * (r + 1);
                }
            }
        }
        return ans;
    }
}