FilesExpand file tree

 master

/

offer48.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

36 lines (34 loc) · 1.02 KB

 master

/

offer48.java

Copy path

Top

File metadata and controls

• Code
• Blame

36 lines (34 loc) · 1.02 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

import java.util.Arrays;

/**

* [48] 最长不含重复字符的子字符串

*

* 题目: 返回给定字符串中最长的不包含重复字符的子字符串的长度.

*

* 思路: 滑动窗口.

*/

class Solution {

/**

* 时间复杂度: O(n)

* 空间复杂度: O(1)

*/

public int lengthOfLongestSubstring(String s) {

int[] preIndex = new int[128];

Arrays.fill(preIndex, -1);

// initial window size is zero, [0, -1].

int left = 0, right = -1;

int maxLength = 0;

// expand the right edge,

// and keep the characters in window don't repeat.

while (right + 1 < s.length()) {

char chr = s.charAt(++right);

// if current character is repeat,

// update left edge.

if (preIndex[chr] != -1) {

left = Math.max(left, preIndex[chr] + 1);

}

maxLength = Math.max(maxLength, right - left + 1);

preIndex[chr] = right;

}

return maxLength;

}

}