Leetcode
Hash Table
Two Pointers
String
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.
Example 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.
分析¶
滑动窗口题,类似于LeetCode 76. Minimum Window Substring。
public int lengthOfLongestSubstring(String s) { if (s == null || s.length() == 0) return 0; int n = s.length(); // 哈希表 int[] map = new int[128]; // 左右指针 int l = 0, r = 0; // 最长子字符串 int maxLength = 0; // 左右字符 char cr, cl; while (r < n) { cr = s.charAt(r); map[cr]++; // 子字符串不重复,满足要求 if (map[cr] == 1) { // 子字符串长度是否比目前发现的最长字符串还长? if (r - l + 1 > maxLength) maxLength = r - l + 1; } else { // 移动左指针,直到不重复 while (true) { cl = s.charAt(l); map[cl]--; l++; if (cl == cr) break; } } r++; } return maxLength; }
近期评论