leetcode03——无重复字符的最长子串

自己的写法

//自己的做法:偏暴力解法,每次只挪动一下左指针或者右指针,在挪动右指针的时候记录下当前最大值
public static int lengthOfLongestSubstring(String s) {
  if (s.length() < 2)
      return s.length();
  int left = 0, right = 1;
  int res = 0;
  while (right <= s.length()) {
    if (isNoRepeat(s.substring(left, right))) {
        res = Math.max(res, (right - left));
        right++;
    } else {
        left++;
    }
  }
  return res;
}

private static boolean isNoRepeat(String str) {
  HashSet<Character> hashSet = new HashSet<>();
  for (char c : str.toCharArray()) {
    if (hashSet.contains(c)) {
        return false;
    }
    hashSet.add(c);
  }
  return true;
}

官方的做法

//官方解法:滑动窗口思想,右指针移动到不能再移动,移动左指针,释放左窗口
public int lengthOfLongestSubstring1(String s) {
  HashSet<Character> hashSet = new HashSet<>();
  int n = s.length();
  //右指针,初始值为-1,相当于在我们的字符串左边,还没有开始移动
  int rk = -1, res = 0;
  for (int i = 0; i < n; i++) {
      if (i != 0) {
          hashSet.remove(s.charAt(i - 1));
      }
      while (rk + 1 < n && !hashSet.contains(s.charAt(rk + 1))) {
          hashSet.add(s.charAt(rk + 1));
          rk++;
      }
      //i ~ rk 是一个无重复子串
      res = Math.max(res, rk - i + 1);
  }
  return res;
}

滑动窗口的应用场景

输入是线性的数据结构,如链表、字符串、数组,要求查找最长/最短子串、子数组、链表中的值;

可处理以下问题

1、大小为k的子数组最大和

2、带有k个不同字符的最长字串

3、寻找字符相同但排序不一样的字符串

双指针滑动窗口解法

右指针右移,移到不能移动为止;

然后左指针左移,释放窗口左边界;

上一篇:HashMap和HashSet的不同之处简介说明


下一篇:No.532 数组中的 k-diff 数对