c++-c++编程基础之leetcode题解第3题无重复字符的最长子串.zip资源-CSDN下载

共1个文件

md：1个

需积分: 1 38 浏览量 2024-03-18 04:56:28 上传评论收藏 2KB ZIP 举报

在C++编程中，LeetCode是一个非常受欢迎的在线平台，用于练习和提升编程技能，特别是算法和数据结构。本资源包聚焦于LeetCode中的第3题——"无重复字符的最长子串"（Longest Substring Without Repeating Characters）。这道题目是字符串处理的经典问题，对理解C++中的字符串操作、滑动窗口算法以及动态规划有很好的实践价值。题目描述：给定一个字符串`s`，找出不包含重复字符的最长子串的长度。你可以假设`s`的字符集范围是`['a'-'z']`，且字符都是小写字母。解题思路： 1. **滑动窗口算法**：这是解决此问题的一种常见方法。我们可以使用两个指针，一个代表窗口的起始位置，另一个代表窗口的结束位置。在每一步，我们向右移动结束指针，检查新加入的字符是否已经在窗口内。如果不在，我们就更新最长子串的长度；如果在，我们就将起始指针向右移动，直到找到一个不在窗口内的字符。这个过程会形成一个动态的、没有重复字符的窗口。 2. **哈希表**：为了实现滑动窗口，我们需要快速检查字符是否已经存在于窗口内。可以使用哈希表（如std::unordered_set）来存储已见过的字符及其出现的位置，这样查询时间复杂度为O(1)。 3. **动态规划**：虽然滑动窗口是更直观的解决方案，但也可以使用动态规划。定义dp[i]为以i结尾的最长无重复字符子串的长度，然后通过遍历字符串，更新dp数组。然而，这种解决方案的空间复杂度较高，不如滑动窗口方法。 4. **优化**：为了进一步提高效率，可以在移动结束指针时，先检查新字符是否已经在哈希表中，避免不必要的移动起始指针的操作。代码实现：在C++中，可以使用以下代码结构来解决这个问题： ```cpp #include <string> #include <unordered_set> int lengthOfLongestSubstring(std::string s) { std::unordered_set<char> seen; int start = 0, max_len = 0; for (int end = 0; end < s.size(); ++end) { if (seen.find(s[end]) != seen.end()) { start = std::max(start, seen[s[end]] + 1); } seen.insert(s[end]); max_len = std::max(max_len, end - start + 1); } return max_len; } ``` 在这个代码中，我们用`seen`哈希表记录每个字符第一次出现的位置，当遇到重复字符时，更新起始位置为重复字符的下一个位置。同时，每次我们更新`max_len`以保存最长子串的长度。这个压缩包文件`c++_c++编程基础之leetcode题解第3题无重复字符的最长子串`很可能包含了对此题目的详细解答，包括代码实现、测试用例以及可能的优化策略。学习这个题目的解法不仅可以加深对C++的理解，也有助于提高在算法竞赛或面试中的表现。

资源推荐

资源详情

资源评论

收起资源包目录

c++_c++编程基础之leetcode题解第3题无重复字符的最长子串.zip （1个子文件）

c++_c++编程基础之leetcode题解第3题无重复字符的最长子串

README.md 5KB

# [3. Longest Substring Without Repeating Characters (Medium)](https://leetcode.com/problems/longest-substring-without-repeating-characters/) Given a string, find the length of the longest substring without repeating characters. <div> Example 1: <pre>Input: "abcabcbb" Output: 3 Explanation: The answer is <code>"abc"</code>, with the length of 3. </pre> <div> Example 2: <pre>Input: "bbbbb" Output: 1 Explanation: The answer is <code>"b"</code>, with the length of 1. </pre> <div> Example 3: <pre>Input: "pwwkew" Output: 3 Explanation: The answer is <code>"wke"</code>, with the length of 3. Note that the answer must be a substring, <code>"pwke"</code> is a subsequence and not a substring. </pre> </div> </div> </div> **Companies**: [Amazon](https://leetcode.com/company/amazon), [Google](https://leetcode.com/company/google), [Bloomberg](https://leetcode.com/company/bloomberg), [Facebook](https://leetcode.com/company/facebook), [Microsoft](https://leetcode.com/company/microsoft), [Adobe](https://leetcode.com/company/adobe), [Apple](https://leetcode.com/company/apple), [Alibaba](https://leetcode.com/company/alibaba), [Uber](https://leetcode.com/company/uber), [ByteDance](https://leetcode.com/company/bytedance), [Cisco](https://leetcode.com/company/cisco), [Huawei](https://leetcode.com/company/huawei), [Zillow](https://leetcode.com/company/zillow), [Yahoo](https://leetcode.com/company/yahoo), [Grab](https://leetcode.com/company/grab), [eBay](https://leetcode.com/company/ebay), [Twitch](https://leetcode.com/company/twitch), [Atlassian](https://leetcode.com/company/atlassian) **Related Topics**: [Hash Table](https://leetcode.com/tag/hash-table/), [Two Pointers](https://leetcode.com/tag/two-pointers/), [String](https://leetcode.com/tag/string/), [Sliding Window](https://leetcode.com/tag/sliding-window/) **Similar Questions**: * [Longest Substring with At Most Two Distinct Characters (Hard)](https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/) * [Longest Substring with At Most K Distinct Characters (Hard)](https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/) * [Subarrays with K Different Integers (Hard)](https://leetcode.com/problems/subarrays-with-k-different-integers/) ## Solution 1. Hash Map ```cpp // OJ: https://leetcode.com/problems/longest-substring-without-repeating-characters/ // Author: github.com/lzl124631x // Time: O(N) // Space: O(C) where C is the range of character set // Ref: https://discuss.leetcode.com/topic/24739/c-code-in-9-lines class Solution { public: int lengthOfLongestSubstring(string s) { int ans = 0, start = -1; vector<int> m(128, -1); for (int i = 0; i < s.size(); ++i) { start = max(start, m[s[i]]); m[s[i]] = i; ans = max(ans, i - start); } return ans; } }; ``` ## Solution 2. Sliding Window Check out "[C++ Maximum Sliding Window Cheatsheet Template!](https://leetcode.com/problems/frequency-of-the-most-frequent-element/discuss/1175088/C%2B%2B-Maximum-Sliding-Window-Cheatsheet-Template!)". Shrinkable Sliding Window: ```cpp // OJ: https://leetcode.com/problems/longest-substring-without-repeating-characters/ // Author: github.com/lzl124631x // Time: O(N) // Space: O(C) class Solution { public: int lengthOfLongestSubstring(string s) { int i = 0, j = 0, N = s.size(), cnt[128] = {}, dup = 0, ans = 0; while (j < N) { dup += ++cnt[s[j++]] == 2; while (dup) dup -= --cnt[s[i++]] == 1; ans = max(ans, j - i); } return ans; } }; ``` Non-shrinable Sliding Window: ```cpp // OJ: https://leetcode.com/problems/longest-substring-without-repeating-characters/ // Author: github.com/lzl124631x // Time: O(N) // Space: O(C) class Solution { public: int lengthOfLongestSubstring(string s) { int i = 0, j = 0, N = s.size(), cnt[128] = {}, dup = 0; while (j < N) { dup += ++cnt[s[j++]] == 2; if (dup) dup -= --cnt[s[i++]] == 1; } return j - i; } }; ``` ## Discuss https://leetcode.com/problems/longest-substring-without-repeating-characters/discuss/1499836/C%2B%2B-Sliding-Window-(%2B-Cheat-Sheet)

评论收藏

内容反馈