LeetCode刷题笔记(三）无重复字符的最长子串

分手后的思念是犯贱 2022-05-27 10:42 173阅读 0赞

题目：

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

**示例：**

给定 `"abcabcbb"` ，没有重复字符的最长子串是 `"abc"` ，那么长度就是3。

给定 `"bbbbb"` ，最长的子串就是 `"b"` ，长度是1。

给定 `"pwwkew"` ，最长子串是 `"wke"` ，长度是3。请注意答案必须是一个**子串**，`"pwke"` 是 *子序列  *而不是子串。

解题1：

class Solution {
        public int lengthOfLongestSubstring(String s) {
            int len = s.length();
            String result = "";   //最长的不重复子串
            String str = "";      //子串
            for(int i=0;i<len;i++){
                for(int j=i+1;j<=len;j++){
                    str = s.substring(i,j);    //嵌套循环截取子串
                    if(j==len){                //截取带最后进行对比
                        result = result.length()<str.length()?str:result;
                        break;
                    }else{                     //如果没有到最后就判断下一位是否在子串中
                        if(str.indexOf(s.substring(j,j+1))>-1){
                           result = result.length()<str.length()?str:result;
                           break;
                        }
                    }
                }
            }
            return result.length();
        }
    }

这是我自己的解法：首先要理解一个思路，如果\[i,j\]是不重复的，那么要判断\[i,j+1\]是否重复，就只要判断\[j+1\]在\[i,j\]是否存在。个越界检查。

这里的计算就是：设'abcabcbb',len=8,

从(0,1)（含左不含右）开始，不等于len，进入else条件，'a'不包括下一个字符'b'，依次循环，

到了(0,3)的时候，str="abc"，包含下一个字符'c'，result="abc",跳出循环，

进入(1,2)，str="b"，一直到(1,4)，包含下一个字符'b'，result长度等于str长度，所以result不变。跳出循环，

进入(2,3)，str="c"，依次循环，最后一直到最后str的长度也没有超过result。最终得出result为abc，所以长度为3

时间复杂度：O(n^2)

空间复杂度：O(n^2)

解法2：

public class Solution {
        public int lengthOfLongestSubstring(String s) {
            int n = s.length();
            Set<Character> set = new HashSet<>();    //存放窗口元素
            int ans = 0, i = 0, j = 0;              //ans不重复子串长度，i是头节点，j是尾节点
            while (i < n && j < n) {
                // try to extend the range [i, j]
                if (!set.contains(s.charAt(j))){      //不包含下一位字符就把尾节点后移一位，窗口+1,并且判断最长子串的长度
                    set.add(s.charAt(j++));
                    ans = Math.max(ans, j - i);
                }
                else {
                    set.remove(s.charAt(i++));        //包含下一位就把头节点后移到尾节点的前一位，窗口重新置为1
                }
            }
            return ans;
        }
    }

滑动窗口思想：其实这个和上面的思路是一样的，就是判断\[i,j\]和\[j+1\]是否重复的问题

若重复：头节点后移到尾节点前一位，滑动窗口大小重定义为1。

若不重复：滑动窗口头不变，结尾+1，整个窗口加大1个单位。继续比较下一个。

时间复杂度：O(n^2)；

空间复杂度：O(n);

解法3：

public class Solution {
        public int lengthOfLongestSubstring(String s) {
            int n = s.length(), ans = 0;
            Map<Character, Integer> map = new HashMap<>();    //存放字符数组和索引，key:char,value:index
            for (int j = 0, i = 0; j < n; j++) {
                if (map.containsKey(s.charAt(j))) {
                    i = Math.max(map.get(s.charAt(j)), i);   //包含下一个字符就把i移到相同字符的后一个位置
                }
                ans = Math.max(ans, j - i + 1);             //判断长度是否要改变
                map.put(s.charAt(j), j + 1);                //把字符和索引放进map，重复的会进行覆盖
            }
            return ans;
        }
    }

这是一直利用HashMap解题思路:其实也是判断\[i,j\]和\[j+1\]的问题。

举个例子：s="abcbadca"; i= 0;j=0

依次把\{a:1,b:2,c:3\}存入map，此时ans = 3,i=0,j=3;

下一次进入的时候，因为‘b'已存在map中，所以i会被设为2，即字符数组中第一个b的后一个位置。同时map里面的b对应的值会被更新为4，然后判断ans的值，同时map里面的b对应的值会被更新为4。

依次计算，就可以把最长不重复子串的长度得出。这里只有一个循环，map的查找时间复杂度为O(1)，比之前的两种方法都快。

时间复杂度：O(n)；

空间复杂度：O(n)

解法4：

public class Solution {
        public int lengthOfLongestSubstring(String s) {
            int n = s.length(), ans = 0;
            int[] index = new int[128]; // current index of character
            for (int j = 0, i = 0; j < n; j++) {
                i = Math.max(index[s.charAt(j)], i);
                ans = Math.max(ans, j - i + 1);
                index[s.charAt(j)] = j + 1;
            }
            return ans;
        }
    }

这个解法和上面的HashMap的解法其实是一样的，只不过这种解法是把之前map的key作为数组的索引，value作为数组的值。因为字符char会被转为int值(根据ASCII码表对应)。不过这种的优势在于只要一个128的数组，而不是map的结构。

时间复杂度：O(n)；

空间复杂度：O(1);