博客

LeetCode 3.无重复子串

下面展示一些

解题思路

。

1.暴力算法

// 1. 暴力解法：遍历数组的所有的区间，然后找到最长没有重复字符的区间

// 时间复杂度：O(n^3)

// 空间复杂度：O(n)

package LeetCode;

import java.util.HashSet;
import java.util.Set;
class  Solution {
    public int lengthOfLongestSubstring1(String s) {
        int n = s.length();
        if (n <= 1) return n;
        int maxLen = 1;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (allUnique(s, i, j)) {
                    maxLen = Math.max(maxLen, j - i + 1);  
                }
            }
        }
        return maxLen;
    }

    private boolean allUnique(String s, int start, int end) {
        Set<Character> set = new HashSet<>();
        for (int i = start; i <= end; i++) {
            if (set.contains(s.charAt(i))) {   //如果set里面包含重复的字符，返回false
                return false;    
            }
            set.add(s.charAt(i));     //否则添加字符到set集合
        }
        return true;
    }
}

2.窗口

暴力解法存在重复计算，同一个子串会进行多次判断 【是否存在重复字符】

我们可以做如下的优化：

如果 s[i, j) 子串没有重复字符的话，那么如果要判断 s[i, j] 没有重复字符的话，我们只需要判断 s[i, j) 中是否存在 s[j] 即可

参考链接

.

window变量为left与right之间的长度 ，无重复子串的大小至少有一个，所以maxLen=1,

class Solution {
    public static void main(String[] args) {
          String str = "pwwkew";
          int a= lengthOfLongesSubstring(str);
        System.out.println(a);
    }
    public  static  int lengthOfLongesSubstring(String s){
        int n=s.length();
        if (n<=1)return  n;
        int maxLen=1;
        int left =0,right=0;
        Set<Character>window =new HashSet<>();
        while (right<n){    //这里用while,一直left向右移动，找到跟set集合里面不同的字符串，通过left移动改变窗口大小，并且移除与set集合里面相同的字符，即right所指向的字符
             char rightchar=s.charAt(right);
             while (window.contains(rightchar)){
                  window.remove(s.charAt(left));
                  left++;
             }
             maxLen=Math.max(maxLen,right-left+1);
             window.add(rightchar);
             right++;

        }
       return  maxLen;
    }
}