2018-08-22

leetcode 3 Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters:题目链接

方法1：暴力解法

利用hashset来判断在[i,j]区间内有无重复元素

import java.util.HashSet;
import java.util.Set;

public class Solution1 {
    // 时间复杂度O(N^2)    空间复杂度O(set的大小*s的大小)
    public int lengthOfLongestSubstring(String s) {
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < s.length(); ++i) {
            // 创建hashset判断[i,j]之间是否有重复元素
            Set<Character> set = new HashSet();
            for (int j = i; j < s.length(); ++j) {
                if (set.contains(s.charAt(j))) {    // 如果有重复元素 终止当前循环 判断[i+1,j]之间是否有重复元素
                    break;
                }
                set.add(s.charAt(j));               // 如果set中不含当前元素 将当前元素添加进set中
                res = Math.max(j - i + 1, res);     // 更新结果
            }
        }
        return res == Integer.MIN_VALUE ? 0 : res;
    }

    public static void main(String[] args) {
        String s = "abcabcbb";
        System.out.println(new Solution1().lengthOfLongestSubstring(s));
    }
}

方法2：双指针之滑动窗口

维持一个窗口[left,right)使这个窗口里面的元素不重复
基本思路:[left,right)中没有重复元素，right++,并将该元素对应出现的频率++,直到right对应元素的频率不为0(即在[left,right)中已有该元素)，记录此时在[left,right)区间元素的个数(选取最大值),left对应元素的频率--，并且left++，直到发现此时right对应元素的频率为0

初始时：left,right都指向第一个元素,此时a,b,c出现的频率都是0

当遇到重复元素时：如图所示，在right遍历的过程中,[left,right)这个左闭右开区间中，a,b,c出现的次数为 a:1 、b:1 、c:1,此时right指向的元素是a,检测发现a之前在[left,right)中出现过，故将left对应元素的频率- -，left++,此时a:0 、b:1 、c:1,发现right指向的元素频率为0了，right++,对应元素的频率++

利用HashMap实现：

import java.util.HashMap;
import java.util.Map;

public class Solution2 {
    // 时间复杂度O(N)  
    public int lengthOfLongestSubstring(String s) {
        int left = 0, right = 0;                        // [left,right):存放无重复元素
        Map<Character, Integer> map = new HashMap<>();
        int res = Integer.MIN_VALUE;

        while (right < s.length()) {
            // 如果map中不含当前元素, 将当前元素添加进map,对应频率+1,并且right往后移
            if (right < s.length() && !map.containsKey(s.charAt(right))){
                map.put(s.charAt(right++), 1);
            }else{  // 如果map中发现当前元素在[left,right)中已经出现过  将left对应元素频率--，left向后移动
                map.remove(s.charAt(left++));
            }
            res = Math.max(res, right - left);   // 更新结果
        }
        return res == Integer.MIN_VALUE ? 0 : res;
    }

    public static void main(String[] args) {
        String s = "abcabcbb";
        System.out.println(new Solution2().lengthOfLongestSubstring(s));
    }
}

不用HashMap使用哈希表,即数组，解法跟用hashMap的一样，只是利用的是数组来记录频率

int[26]       for Letters 'a' - 'z' or 'A' - 'Z'
int[128]      for ASCII
int[256]      for Extended ASCII

public class Solution3 {
    // 时间复杂度O(N)  空间复杂度O(M) M:字符集的长度 即声明ascii数组大小
    public int lengthOfLongestSubstring(String s) {
        int left = 0, right = 0;         // [left,right)
        int[] ascii = new int[256];
        int res = Integer.MIN_VALUE;
        while (right < s.length()) {
            if (right < s.length() && ascii[s.charAt(right)] == 0) {
                ascii[s.charAt(right++)]++;
            } else {
                ascii[s.charAt(left++)]--;
            }
            res = Math.max(res, right - left);
        }
        return res == Integer.MIN_VALUE ? 0 : res;
    }

    public static void main(String[] args) {
        String s = "abcabcbb";
        System.out.println(new Solution3().lengthOfLongestSubstring(s));
    }
}

pS: 源代码链接

本文标题:leetcode 3 Longest Substring Without Repeating Characters

文章作者:XerDemo

发布时间:2018-08-22, 15:24:00

最后更新:2018-08-22, 16:37:22

原始链接:https://xerdemo.github.io/2018/08/22/LeetCode解题/01-Array/leetcode-3-Longest-Substring-Without-Repeating-Characters/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。