LeetCode-0003 Longest Substring Without Repeating Characters

原题地址

题目:

Given a string, find the length of the longest substring without repeating characters.

例子1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

例子2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

例子3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

题目大意:
给定一个字符串,返回最长的不重复子串的长度。

解法一
两层遍历,下标分别为iijj,如果字符串sijs_{ij}之间没有重复字符的话,计算出ijij之间的长度,与当前最大长度totaltotal比较,如果大于totaltotal则用sijs_{ij}的长度更新totaltotal, 最后返回total即可

scala代码如下:

object Solution { def lengthOfLongestSubstring(s: String): Int = { var total = 0 for(i <- s.indices){ val arr: Array[Int] = Array.fill(128)(-1) var curr = 0 for(j <- (i + 1) until s.length+1){ val c = s.charAt(j-1) if(arr(c) >= 0){ curr = 0 }else{ curr += 1 total = if(curr > total) curr else total arr(c) = j } } } total } }

上述代码值得注意的地方是如何判断某个字符串是否含有重复字符,借助数组可以很巧妙的实现判断字符是否含有重复字符,其中数组的长度为128, 下标为字符转为数组的值,数组的值为该字符在字符串的索引。
例如字符串s="abda", 记录’a’的位置可以: arr('a')=0, 当最后一次读到的a的时候只需要判断arr('a') >=0是否成立便知道读取到的当前字符是否与前面的字符串中的某个字符相同。

时间复杂度计算公式为:

O(i=1nj=in1)O(\sum_{i=1}^{n}\sum_{j=i}^n1)

其中:

i=1nj=in1=i=1n(ni+1)=i=1n(n+1)i=1ni=n(n+1)n(n+1)2=n(n+1)2\sum_{i=1}^{n}\sum_{j=i}^n1 = \sum_{i=1}^n(n-i+1)=\sum_{i=1}^n(n+1) - \sum_{i=1}^ni=n(n+1)-\frac{n(n+1)}{2} = \frac{n(n+1)}{2}

所以时间复杂度为:

O(i=1nj=in1)=O(n(n+1)2)=O(n2)O(\sum_{i=1}^{n}\sum_{j=i}^n1)=O(\frac{n(n+1)}{2})=O(n^2)

解法二
借助滑动窗口的思想,设begin为所求字符串的头索引,end为尾索引,最开始begin=end=0, 逐步增加end的值,并判断end加一后的字符sends_{end}是否与字符串sbegin,ends_{begin,end}

scala代码如下:

object Solution { def lengthOfLongestSubstring(s: String): Int = { var total = 0 var begin = 0 val arr: Array[Int] = Array.fill(256)(-1) for(end <- s.indices){ val c = s.charAt(end) if(arr(c) >= 0 && arr(c) >= begin){ begin = arr(c) + 1 arr(c) = end }else{ arr(c) = end } val length = end - begin + 1 if(length > total){ total = length } } total } }

载入评论中....