当前位置: 代码迷 >> 综合 >> [LeetCode] Longest Substring Without Repeating Characters | Two Pointers + Hash Map
  详细解决方案

[LeetCode] Longest Substring Without Repeating Characters | Two Pointers + Hash Map

热度:97   发布时间:2023-12-22 05:40:02.0

https://leetcode.com/problems/longest-substring-without-repeating-characters/?tab=Description

要求在一个字符串中寻找最长的没有重复字符的子串。注意,是子串(substring),不是子序列(subsequence)。

思路1:Brute Force

暴力的做法简而言之就是:遍历字符串所有的位置,以这个位置为起点往前走,找出满足要求的子串。

具体地,可以用两个指针维护子串的区间,每往前走一格,须要判断当前位置的字符在区间内是否重复出现(暴力的做法是扫描这个区间,较好的做法是用一个Hash Set存储区间内的元素,从而可以O(1)查找)。

Time complexity: 最最暴力的算法是O(n^3),用Hash Set的话就是O(n^2)
Space complexity: 用Hash Set的话就是O(字符种类数),否则O(1)

ps. O(n^2)的算法可以AC

参考代码(C++)

class Solution { public:int lengthOfLongestSubstring(string s) {int n = s.size();if (n == 0) return 0;if (n == 1) return 1;int ret = 1;int start = 0, end = 1;while (end < n) {int tmp_ret = 1;unordered_set<int> myset({s[start]});while (end < n && myset.find(s[end]) == myset.end()) {myset.insert(s[end]);tmp_ret++;end++;}ret = max(ret, tmp_ret);start++; end = start + 1;}return ret;} };

思路2:Sliding Window / Two Pointers

将longest substring without repeating characters简称为"LSWRC"。

扫描一遍字符串,对每个位置,计算以该位置的字符为终点的LSWRC的长度,取最大的。

具体地,设字符串为s,用s[i]表示位置i的字符,设以s[i]为终点的LSWRC的长度对应的区间是[start, i]。然后据此计算位置i+1的LSWRC,分两种情况:

  1. 如果s[i+1]s[start...i]未出现,则新的区间为[start, i+1]
  2. 如果s[i+1]s[start...i]出现了,设出现的位置是p (start <= p <= i),则须要更新区间为[p+1, i+1]

实现上,可以用两个变量维护区间的边界信息,用一个哈希表存储区间的元素以快速查找。这里有一个小技巧,不需要真的去存区间的元素,否则还要删除(虽然删除的开销并不大),直接存目前为止的所有元素,查找的时候如果找到了重复元素,再判断找到的元素是否在[start, i]区间内即可,不在的话就按情况1更新区间。

Time complexity: O(n)
Space complexity: O(字符种类数)

参考代码(C++)

class Solution { public:int lengthOfLongestSubstring(string s) {int n = s.size();if (n == 0) return 0;if (n == 1) return 1;int ret = 1, cur_ret = 1;unordered_map<char, int> hash_map; // key: element of s, value: index of the elementhash_map[s[0]] = 0;int start = 0;for (int i = 1; i < n; ++i) {unordered_map<char, int>::iterator it = hash_map.find(s[i]);if (it == hash_map.end()) {hash_map[s[i]] = i;} else {if (it->second >= start) {start = it->second + 1;}it->second = i; // update the pos of repeated char}ret = max(ret, i-start+1);}return ret;} };

转载于:https://www.cnblogs.com/ilovezyg/p/6413081.html

  相关解决方案