LeetCode3 无重复字符的最长子串

Substring refers to substrings concatenated together,The subsequence don't have to get together every element,As long as the priority order of the elements is satisfied.例如：pwwkew,Its not repeat sequence can bewke,kew,But its non-repetitive subsequence can bepwke.

题目描述

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

示例

示例1：

输入：“abcabcbb"

输出：3

解释：解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3.

示例2：

输入：“bbbbb”

输出：1

解释：因为无重复字符的最长子串是 “b”,所以其长度为 1.

示例3：

输入： “pwwkew”

输出：3

解释：因为无重复字符的最长子串是 “wke”,所以其长度为 3.

提示：哈希表,双指针,字符串,Sliding Window(滑动窗口)

题目解析

  According to the topic given,can be written using the sliding window trick,The sliding window technique itself is used to find some continuous extreme values ​​in a string or array,For example the longest substring length here.The question now is when can we expand the size of the sliding window？很明显,When the next character is inconsistent with the character in the current sliding window,Should broaden its.And when should you reduce the size of the sliding window?？when there is repetition,All elements to the left of the repeated characters in the sliding window should be deleted,In this process, as long as the maximum value of the sliding window is recorded, the correct answer can be obtained..

  When the sliding window is implemented, the left and right pointers are generally used to define the boundary of the sliding window.,假设这里我们使用leftto represent the left border of the sliding window,rightto represent the right edge of the sliding window,The length of the sliding window is（right - left）.Now turn the question into when to increaseleft（缩小窗口）,when to increaseright(扩大窗口),The process is the same as described above.

解法一：

  The code implementation can use some collection framework to save the array in the sliding window,This makes it easier for us to determine whether an element is in the sliding window,Of course we use an array to save,It is also possible to delete the data you want to delete after making your own judgment..使用set集合的代码如下：

class Solution {
    
    public int lengthOfLongestSubstring(String s) {
    
        if (s.length() == 0) {
    
            return 0;
        }
        int maxLen = 0;		//Record the maximum value of the sliding window
        int left = 0, right = 0;	//滑动窗口的左边界和右边界
        Set<Character> set = new HashSet<>();
        while (left < s.length() && right < s.length()) {
    
            if (!set.contains(s.charAt(right))) {
    	//判断setWhether there are repeated characters in the set
                set.add(s.charAt(right));
                right++;	//Sliding window elements and expanding the scope of the sliding window is added
                maxLen = Math.max(maxLen, right - left);
            } else {
    
                set.remove(s.charAt(left));	//The characters in it will remove them one by one to the position of the repeating element
                left++;
            }
        }
        return maxLen;
    }
}

程序的运行结果：

解法二：

其实上述setThe lookup done by the collection can be completely replaced by writing a loop ourselves,而且也比较好理解,代码如下：

  class Solution {
    
    public int lengthOfLongestSubstring(String s) {
    
  		if (s.length() == 0) {
    
            return 0;
        }

        int maxLen = 1;		//If the program is executed,则串s中至少有一个元素
        int left = 0, right = 1;
       while (right < s.length()){
    
            int index = -1;
            for (int j = right - 1; j >= left; j--) {
    	//模拟setThe process of collection to find elements,Find the subscript of the current recurring element from the back to the front
                if (s.charAt(right) == s.charAt(j)) {
    
                    index = j;
                    break;
                }
            }
            if (index != -1) {
    
                left = index + 1;	//The left border of the new window should be the next bit of the repeated element
            }
            right++;
            maxLen = Math.max(maxLen, right - left);
       }
       return maxLen;
   }
}

  程序运行结果：It can be seen from the code that the worst time complexity should beO(n2)的,And the performance of traversal lookup is notsetGood performance for finding an element in a collection,Therefore, rather than usingsetThe way to gather is a lot slower.

解法三

  At this point, we can already find that the key to solving this problem is how to quickly find the same element as the current traversed element from the elements in the existing sliding window.,The time complexity of the above two methods isO(logn)和O(n)级别.And a faster way to lookup is to use a hash table,It can be achieved without conflictO(1)的时间复杂度,快了很多.And the string given in the question is at most only256个,and there is no conflict,So it is possible to create a size of256的数组,Its subscript is the corresponding characterASCII码的值,**And the value stored in the array is the position of the last occurrence of the character（从1开始,Because the array is initially0,Saving index values ​​may cause code to run incorrectly）**代码如下：

  class Solution {
    
    public int lengthOfLongestSubstring(String s) {
    
		if (s.length() == 0) {
    
            return 0;
        }
        int[] hash = new int[256];
        int maxLen = 0;
        int left = 0, right = 0;
        while (left < s.length() && right < s.length()) {
    
            char c = s.charAt(right);
            left = Math.max(left, hash[c]);		//Get the position of the last occurrence of the current character in the sliding window（This is equivalent to the above process,直接 使用O(1)The time complexity of
            maxLen = Math.max(maxLen, right - left + 1);
            hash[c] = ++right;	//keep the position of the last occurrence of the element
        }
        return maxLen;
    }
  }

程序运行结果：

It can be seen that it is better to usesetSet almost doubled~