Leetcode算法Java全解答--3. 无重复字符的最长子串

Posted by lizhao on 10-11,2018

Leetcode算法Java全解答–3. 无重复字符的最长子串

文章目录

  • Leetcode算法Java全解答--3. 无重复字符的最长子串
    • 题目
    • 想法
    • 结果
    • 总结
    • 代码
      • 我的答案
      • 大佬们的答案
      • 测试用例
    • 其他

题目

无重复字符的最长子串

题目

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

示例 1:

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

示例 2:

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

示例 3:

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

想法

  1. 暴力破解:锁定位置i、j,判断i和j之间是否有重复串,时间复杂度n3
  2. 滑动列表:还是锁定i、j,不过在遍历的同时,

如果未发现重复字符串,将j往后移

如果发现重复字符串,将i往后移

判断重复使用的是HashSet

结果

执行用时:71 ms

超过41%的解法

时间复杂度n

空间复杂度n

总结

NOT_ANSWER
自己想出来的方法就是暴力破解

有想到加载过的字符不用重复,但是没有书写代码的思路

小批量字符可以使用数组代替hashSet

代码

我的答案

   public int lengthOfLongestSubstring(String s) {
    int n = s.length();
    HashSet<Character> characters = new HashSet<>();
    int result = 0;
    int i = 0;
    int j = 0;

    while (i < n && j < n) {
      if (!characters.contains(s.charAt(j))) {
        characters.add(s.charAt(j));
        j++;
        result = Math.max(result, j - i);
      } else {
        characters.remove(s.charAt(i));
        i++;
      }
    }

    return result;
  }

大佬们的答案

  /**************************************
   * 比我好的答案 better
   * 这里使用了int[]代替了HashSet
   * ***********************************/
  public int better(String s) {
    int n = s.length(), ans = 0;
    int[] index = new int[128]; // current index of character
    // try to extend the range [i, j]
    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;

  }

测试用例

  @Test
  public void test003() {
    // 创建测试案例
    String s1 = "abcabcbb";
    String s2 = "bbbbb";
    String s3 = "pwwkew";

    // 测试案例期望值
    int expResult1 = 3;
    int expResult2 = 1;
    int expResult3 = 3;

    // 执行方法
    Solution3 solution3 = new Solution3();
    int result1 = solution3.lengthOfLongestSubstring(s1);
    int result2 = solution3.lengthOfLongestSubstring(s2);
    int result3 = solution3.lengthOfLongestSubstring(s3);

    // 判断期望值与实际值
    Assert.assertEquals(expResult1, result1);
    Assert.assertEquals(expResult2, result2);
    Assert.assertEquals(expResult3, result3);

  }

其他

代码托管码云地址: https://gitee.com/lizhaoandroid/LeetCodeAll.git

查看其他内容可以点击专栏或者我的博客哈: https://blog.csdn.net/cmqwan

“大佬们的答案” 标签来自leetcode,侵权请联系我进行删改

如有疑问请联系,联系方式:QQ3060507060