Leetcode(3) - 无重复字符的最长子串 - java版

Leetcode(3) - 无重复字符的最长子串 - java版

题目

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

示例1:

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

初次解题分析

暴力方法(此方法由于时间限制,无法通过)

思路:

逐个检查所有的子字符串，看它是否不含有重复的字符。

初步代码实现

class Solution {
  public  int lengthOfLongestSubstring(String s) {
        int strLength = s.length();
        int max = 0;
      // 遍历得到每一个子字符串
        for(int i =0;i<strLength;i++)
            for(int j=i+1;j<=strLength;j++)
                //对每一个子字符串进行判断, 最更新max值
                if(!isRept(s,i,j)) max = Math.max(max,j-i);
        return max;
    }
    // 判断子字符串中是否有重复字符
    public  boolean isRept(String s,int begin,int end){
        Set<Character> charSet = new HashSet<>();
        for(int i=begin;i<end;i++){
            Character x = s.charAt(i);
            if(charSet.contains(x))return true;
            charSet.add(x);
        }
        return false;
    }
}

注意:

for循环的判断条件容易出错,书写时应留意.

---

改进阶段之方法一

具体思路:

滑动窗口

我们可以使用 HashSet 将字符存储在当前窗口 [i,j) 中。 然后我们向右侧滑动索引 j，如果它不在 HashSet 中，我们会继续滑动 ,如果直s[j] 已经存在于 HashSet 中, 我们需要逐个将HashSet中的值remove , 直到将j对应的重复值移出Set,与此同时,索引i右移。

这样做的目的是使所有可能存在的没有重复字符的最长子串都以索引i开头,如果我们对所有的i都这样做,就可以得到最后答案.

实现:

class Solution {
  public  int lengthOfLongestSubstring(String s) {
        Set<Character> charSet = new HashSet<>();
        int i = 0,j = 0,ans = 0,n = s.length();
        while(i<n && j<n){
            if(!charSet.contains(s.charAt(j))){
                charSet.add(s.charAt(j++));
                ans = Math.max(ans,j-i);
            }else{
                charSet.remove(s.charAt(i++));
            }
        }
        return ans;
    }
}

改进阶段之方法二

具体思路:

优化的滑动窗口

上述的方法最多需要执行 2n 个步骤。事实上，它可以被进一步优化为仅需要 n 个步骤。我们可以定义字符到索引的映射，而不是使用集合来判断一个字符是否存在。 当我们找到重复的字符时，我们可以立即跳过该窗口。

实现:

class Solution {
  public  int lengthOfLongestSubstring(String s) {
      Map<Character,Integer> map = new HashMap<>();
      int ans = 0,n = s.length();
      for(int i =0,j = 0;j < n ;j++){
          if(map.containsKey(s.charAt(j))){
            // 注意! 此处map.get(s.charAt(j))获得的值必须与i进行判断,如果不进行判断,则可能出现i索引后退的情况,如参数字符串为abba时.
              i = Math.max(i,map.get(s.charAt(j)));
          }
          ans = Math.max(ans,j-i+1);
          map.put(s.charAt(j),j+1);
      }
      return ans;
    }
}

改进阶段之方法三

具体思路:

替换方法二中的HashMap为整数数组

当我们知道该字符集比较小的时侯，我们可以用一个整数数组作为直接访问表来替换 Map。

解决了方法二种中以空间换时间的尴尬.

实现:

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        int[] index = new int[128]; 
        for (int j = 0, i = 0; j < n; j++) {
            //更新i的值
            i = Math.max(index[s.charAt(j)], i);
            ans = Math.max(ans, j - i + 1);
            // 向保存字符的数组中赋值
            index[s.charAt(j)] = j + 1;
        }
        return ans;
    }
}