每日一练 | Day 4
LCP 40. 心算挑战
题目链接
https://leetcode.cn/problems/longest-substring-without-repeating-characters/
相关算法
哈希表、字符串、滑动窗口
题目描述
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串
的长度。
数据范围：
0 <= s.length <= 5 * 104s由英文字母、数字、符号和空格组成
解题思路
本题要求找出不含有重复字符的子串，然后求出其中最长的的长度，因此，我们可以用滑动窗口法，即维护一个双指针，使得左右指针范围内的所有数组元素都是唯一的。而要保证唯一性，我们可以这样做，使用一个列表存储左右指针范围内的所有元素，当右指针向右移动时，如果指针指向的元素不在列表内，就说明当前窗口符合要求，因此可以考虑更新结果。当出现重复元素时，移动左指针，同时把因为左指针移动变到窗口外的元素移除列表即可。
在本题里面，为了提高列表删除的效率，可以使用哈希的存储结构，此处 java 使用 HashSet 比较合适
完整代码
class Solution {public int lengthOfLongestSubstring(String s) {HashSet<Character> set = new HashSet<>();int left = 0, right = 0;int ans = 0;while (right < s.length()) {if (!set.contains(s.charAt(right))) {set.add(s.charAt(right));right++;ans = Math.max(ans, right - left);} else {set.remove(s.charAt(left));left++;}}return ans;}
}
- 时间复杂度：
O(n) - 空间复杂度：
O(n)