Re: 【leetcode】3. 无重复字符的最长子串

【 在 shaojunying 的大作中提到: 】 : 应该是因为你用的unordered_set 不是按照插入顺序排序的 unroderedset 就是去重且不自动排序。谢谢关注

换成list就可以了

它底层是哈希表 也不是插入顺序 不能确定遍历的顺序 【 在 xxxiaohao 的大作中提到: 】 :

【 在 shaojunying 的大作中提到: 】 : 它底层是哈希表 也不是插入顺序 不能确定遍历的顺序 : : 查了一下资料。答案中的题解也是用的unorderedset，对于其底层原理不清除，但应该是能实现去重加按插入顺序排好的（我一直这么用的啊...）。另外list我查了以后是相当于双向链表的一个序列化容器，没法拥有去重复，判断某个元素是否重复的功能把？

【 在 xxxiaohao 的大作中提到: 】 : : 查了一下资料。答案中的题解也是用的unorderedset，对于其底层原理不清除，但应该是能实现去重加按插入顺序排好的（我一直这么用的啊...）。另外list我查了以后是相当于双向链表的一个序列化容器，没法拥有去重复，判断某个元素是否重复的功能把？ 我看了一下答案 答案是用的occ.erase(s[i - 1]);（删除值为s[i-1]的元素），你用的是st.erase(st.begin()) （删除第一个元素）。答案没有假设unorderedset按插入顺序存储 如果将你的代码改成这样也是可以通过的（修改的地方我都有注释） class Solution { public: int lengthOfLongestSubstring(string s) { unordered_set<char> st; int maxLen = 0; int j=0; for (int i = 0; i < (int)s.length(); i++) { //不重复 一直添加 if (st.count(s[i]) == 0) { st.insert(s[i]); maxLen = max(maxLen, (int)st.size()); } else { //s[i]出现重复 unordered_set<char>::iterator it = st.find(s[i]); //st中存储的其实就是最长不重复子串 while (s[j] != s[i]) { // 修改过 st.erase(s[j]); // 修改过 j++; // 修改过 } //j指向这次重复的字符的下一个下标 st.erase(s[j]); // 修改过 j++; // 修改过 st.insert(s[i]); } } return maxLen; } };

【 在 xxxiaohao 的大作中提到: 】 : : 查了一下资料。答案中的题解也是用的unorderedset，对于其底层原理不清除，但应该是能实现去重加按插入顺序排好的（我一直这么用的啊...）。另外list我查了以后是相当于双向链表的一个序列化容器，没法拥有去重复，判断某个元素是否重复的功能把？ 对于list，假设lt表示一个list对象，可以使用find(lt.begin(), lt.end(), s[i]) == lt.end()确定是否存在重复（本质上仍然是遍历，逐个进行比较）

参考http://www.cplusplus.com/reference/unordered_set/unordered_set/，可以看到这样的描述 Unordered sets are containers that store unique elements in no particular order翻译过来是无序集合是一种容器，它不按特定顺序存储唯一的元素。 你可以运行下这段代码 int main() { unordered_set<int> st; st.insert(15); st.insert(1); st.insert(2); st.insert(3); for (unordered_set<int>::iterator it = st.begin(); it != st.end(); it ++){ cout << *it<<" "; } } 输出为 3 1 2 15 是乱序的

【 在 shaojunying 的大作中提到: 】 : 参考http://www.cplusplus.com/reference/unordered_set/unordered_set/，可以看到这样的描述 Unordered sets are containers that store unique elements in no particular order翻译过来是无序集合是一种容器，它不按特定顺序存储唯一的元素。 : 你可以运行下这段代码 : int main() { : ................... 我执行这段代码...结果是15 1 2 3

【 在 shaojunying 的大作中提到: 】 : 我看了一下答案 答案是用的occ.erase(s[i - 1]);（删除值为s[i-1]的元素），你用的是st.erase(st.begin()) （删除第一个元素）。答案没有假设unorderedset按插入顺序存储 : 如果将你的代码改成这样也是可以通过的（修改的地方我都有注释） : class Solution { : ................... 是可以执行通过。我只是用c++刷题，底层好多细节不清楚23333。但这么可以通过，有些迷惑... unordered_set<int> st; st.insert(15); st.insert(1); st.insert(2); st.insert(8); st.insert(1); st.insert(3); st.erase(st.begin()); st.erase(st.begin()); for (unordered_set<int>::iterator it = st.begin(); it != st.end(); it++) { cout << *it << " "; } 我本地输出的结果是2 8 3.应该可以表明是按顺序存放在unordedset中的把？