LeetCode 三月每日一题

3.26

和相等的子数组

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

• 用哈希表记录两个相邻元素之和，如果哈希表中已经存在，则返回true，否则返回false
• 时间复杂度O(n)，空间复杂度O(n)，n为nums数组长度

  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 中的每一个字符进行比较，如果不同，则分别向左和向右扩展，计算满足条件的子串个数。

  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;
      }
  }