acm竞赛试题及答案

acm竞赛试题及答案ACM竞赛试题及答案一、选择题（共20分）1.下列哪种数据结构最适合实现LRU（最近最少使用）缓存？A.队列B.栈C.哈希表D.哈希表和双向链表组合2.在二叉树的前序遍历、中序遍历和后序遍历中，下列说法正确的是：A.前序遍历和中序遍历可以唯一确定一棵二叉树B.后序遍历和中序遍历可以唯一确定一棵二叉树C.前序遍历和后序遍历可以唯一确定一棵二叉树D.任意两种遍历方式都可以唯一确定一棵二叉树3.对于快速排序算法，下列哪种情况下性能最差？A.待排序数组已经有序B.待排序数组元素完全随机C.待排序数组元素逆序排列D.待排序数组元素全部相同4.在Dijkstra算法中，使用哪种数据结构可以优化性能？A.数组B.队列C.优先队列D.栈5.下列哪种算法不是用于解决图的最短路径问题？A.Dijkstra算法B.Bellman-Ford算法C.Floyd-Warshall算法D.Kruskal算法二、填空题（共20分）1.在二叉搜索树中，对于任意节点，其左子树中所有节点的值_______该节点的值，其右子树中所有节点的值_______该节点的值。2.在动态规划中，重叠子问题是指________，最优子结构是指________。3.在字符串匹配中，KMP算法通过预处理模式串构建________数组，使得在匹配失败时可以直接跳过不必要的比较。4.在拓扑排序中，如果一个有向图中存在环，则该图________进行拓扑排序。5.在贪心算法中，贪心选择性质是指________，最优子结构性质是指________。三、判断题（共10分）1.在平衡二叉搜索树（如AVL树）中，任何节点的两个子树的高度差不超过1。（）2.在B树中，所有叶子节点都位于同一层。（）3.使用邻接矩阵存储图时，空间复杂度为O(V^2)，其中V是顶点数。（）4.在并查集中，路径压缩和按秩合并可以确保操作的时间复杂度为O(1)。（）5.在动态规划中，如果问题满足最优子结构性质，则一定可以使用动态规划解决。（）四、简答题（共20分）1.请解释什么是分治算法，并举例说明分治算法的三个步骤。分治算法在解决哪些类型的问题时特别有效？（10分）2.请解释什么是回溯算法，并描述回溯算法的基本框架。回溯算法与动态规划有何区别？（10分）五、编程题（共30分）1.给定一个整数数组nums和一个目标值target，请找出数组中两个数之和等于target的两个整数，并返回它们的数组下标。假设每种输入只会对应一个答案，且同一个元素不能使用两次。（15分）2.给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。（15分）---ACM竞赛试题及答案一、选择题（共20分）1.答案：D解释：LRU（最近最少使用）缓存是一种缓存淘汰策略，当缓存满时，会淘汰最近最少使用的数据。要实现LRU缓存，需要支持快速查找和快速插入/删除操作。选项A的队列可以记录数据的访问顺序，但查找效率低，需要遍历整个队列。选项B的栈只能记录数据的访问顺序，且只能访问栈顶元素，不适合实现LRU缓存。选项C的哈希表可以提供O(1)的查找时间，但无法记录元素的访问顺序。选项D的哈希表和双向链表结合可以解决这些问题：哈希表用于快速查找，双向链表用于记录元素的访问顺序，最近访问的元素放在链表头部，最久未访问的元素放在链表尾部。当需要淘汰元素时，直接删除链表尾部的元素即可。因此，哈希表和双向链表组合是最适合实现LRU缓存的数据结构。2.答案：B解释：在二叉树中，前序遍历是根-左-右，中序遍历是左-根-右，后序遍历是左-右-根。通过中序遍历可以确定根节点的左右子树，然后通过前序或后序遍历可以进一步确定左右子树的根节点。例如，给定前序遍历序列为[1,2,4,5,3,6,7]，中序遍历序列为[4,2,5,1,6,3,7]。通过前序遍历的第一个元素1可以确定根节点，然后在中序遍历中找到1的位置，可以确定左子树为[4,2,5]，右子树为[6,3,7]。然后对左子树和右子树递归应用相同的方法，可以唯一确定这棵二叉树。同样，给定后序遍历序列为[4,5,2,6,7,3,1]，中序遍历序列为[4,2,5,1,6,3,7]。通过后序遍历的最后一个元素1可以确定根节点，然后在中序遍历中找到1的位置，可以确定左子树为[4,2,5]，右子树为[6,3,7]。然后对左子树和右子树递归应用相同的方法，也可以唯一确定这棵二叉树。但是，给定前序遍历序列[1,2,4,5,3,6,7]和后序遍历序列[4,5,2,6,7,3,1]，我们无法确定左右子树的分界。例如，根节点1的左子树可能是[2,4,5]或[2]，右子树可能是[3,6,7]或[3,6,7]。因此，前序遍历和后序遍历不能唯一确定一棵二叉树。3.答案：A和C解释：快速排序的性能取决于选择的基准元素。快速排序的基本思想是选择一个基准元素，将数组分为两部分，一部分小于基准元素，一部分大于基准元素，然后递归地对这两部分进行排序。在最好的情况下，每次选择的基准都能将数组分成两个大小相等的子数组，时间复杂度为O(nlogn)。在最坏的情况下，每次选择的基准都是数组中的最小或最大元素，导致数组被分成一个大小为n-1的子数组和一个大小为0的子数组，时间复杂度为O(n^2)。当待排序数组已经有序或逆序排列时，如果选择第一个或最后一个元素作为基准，就会导致最坏情况的发生。例如，对于已经有序的数组[1,2,3,4,5]，如果选择第一个元素1作为基准，左子数组为空，右子数组为[2,3,4,5]，然后递归地对右子数组进行排序，每次都会得到一个大小为n-1的子数组和一个大小为0的子数组，导致时间复杂度为O(n^2)。同样，对于逆序排列的数组[5,4,3,2,1]，如果选择第一个元素5作为基准，也会导致最坏情况的发生。如果待排序数组元素全部相同，例如[3,3,3,3,3]，也会导致最坏情况的发生，因为无论选择哪个元素作为基准，左子数组和右子数组的大小都不平衡。4.答案：C解释：Dijkstra算法用于求解带权重的有向图或无向图中的单源最短路径问题。算法的基本思想是维护一个距离数组，记录从源点到每个顶点的最短距离，初始时源点的距离为0，其他顶点的距离为无穷大。然后每次选择距离源点最近的未访问顶点，更新其邻居顶点的距离。使用数组存储距离时，每次选择距离源点最近的未访问顶点需要遍历整个距离数组，时间复杂度为O(V^2)，其中V是顶点数。对于稀疏图（边数远小于V^2的图），这种方法的效率不高。使用优先队列（最小堆）存储距离数组，可以高效地获取距离源点最近的未访问顶点。优先队列的插入和删除操作的时间复杂度为O(logV)，因此总的时间复杂度为O(E+VlogV)，其中E是边数。对于稀疏图，这种方法比使用数组更高效。选项A的数组虽然可以存储距离，但无法高效地获取距离源点最近的未访问顶点。选项B的队列无法保证按照距离排序，因此不适合用于Dijkstra算法。选项D的栈是后进先出的数据结构，与Dijkstra算法的需求不符。5.答案：D解释：Dijkstra算法、Bellman-Ford算法和Floyd-Warshall算法都是用于解决图的最短路径问题。Dijkstra算法用于求解单源最短路径问题，即从源点到其他所有顶点的最短路径。该算法不能处理负权边，时间复杂度为O(E+VlogV)，其中E是边数，V是顶点数。Bellman-Ford算法也用于求解单源最短路径问题，但可以处理负权边。该算法通过松弛操作逐步逼近最短路径，时间复杂度为O(VE)。Floyd-Warshall算法用于求解所有顶点对之间的最短路径，即任意两个顶点之间的最短路径。该算法可以处理负权边，但不能处理负权环。时间复杂度为O(V^3)。Kruskal算法用于求解无向图的最小生成树，而不是最短路径问题。最小生成树是连接图中所有顶点的边的集合，且边的权重之和最小。Kruskal算法的时间复杂度为O(ElogE)，其中E是边数。二、填空题（共20分）1.答案：小于，大于解释：在二叉搜索树中，对于任意节点，其左子树中所有节点的值都小于该节点的值，其右子树中所有节点的值都大于该节点的值。这一性质使得二叉搜索树可以高效地支持查找、插入和删除操作。查找操作从根节点开始，将目标值与当前节点的值比较。如果目标值等于当前节点的值，则查找成功；如果目标值小于当前节点的值，则递归地在左子树中查找；如果目标值大于当前节点的值，则递归地在右子树中查找。如果到达空节点，则查找失败。插入操作与查找类似，从根节点开始，找到合适的插入位置，然后将新节点插入到该位置。删除操作稍微复杂，需要考虑三种情况：a)如果要删除的节点是叶子节点，直接删除即可。b)如果要删除的节点只有一个子节点，用其子节点替换该节点即可。c)如果要删除的节点有两个子节点，找到其右子树中的最小节点（或左子树中的最大节点），用该节点的值替换要删除节点的值，然后删除该节点。2.答案：在递归过程中，相同的子问题被多次求解；问题的最优解包含其子问题的最优解解释：在动态规划中，重叠子问题是指在一个递归算法中，相同的子问题被多次求解，这会导致大量的重复计算。例如，在计算斐波那契数列时，fib(n)=fib(n-1)+fib(n-2)，而fib(n-1)和fib(n-2)又会递归地计算fib(n-2)和fib(n-3)，导致fib(n-2)被计算两次。最优子结构是指问题的最优解包含其子问题的最优解。这意味着我们可以通过求解子问题的最优解来构建原问题的最优解。例如，在背包问题中，物品的最优装载方案包含了前n-1个物品的最优装载方案。动态规划通过存储子问题的解（通常使用数组或哈希表）来避免重复计算，从而提高算法的效率。动态规划有两种实现方式：自顶向下（递归+记忆化）和自底向上（迭代）。3.答案：部分匹配表（或next）解释：KMP算法是一种高效的字符串匹配算法，由Knuth、Morris和Pratt三人提出。其核心思想是利用已经匹配的部分信息来避免不必要的比较，从而提高匹配效率。在KMP算法中，通过预处理模式串构建部分匹配表（也称为next数组），记录模式串中每个位置之前的子串的最长公共前后缀长度。例如，对于模式串"ABABC"，其部分匹配表为[0,0,0,1,2]。在匹配过程中，当发生失配时，根据部分匹配表的值直接将模式串向右移动相应的位置，跳过不必要的比较。例如，当模式串"ABABC"与文本串"ABABDABC"匹配时，当匹配到第五个字符时发生失配（'C'!='D'），根据部分匹配表的值，可以将模式串向右移动3个位置，继续从文本串的第五个字符开始匹配。KMP算法的时间复杂度为O(n+m)，其中n是文本串的长度，m是模式串的长度，比朴素的字符串匹配算法（O(nm)）更高效。4.答案：不能解释：拓扑排序是对一个有向无环图（DAG）的顶点进行排序，使得对于每条有向边(u,v)，顶点u在排序结果中都出现在顶点v之前。拓扑排序可以用于解决任务调度、依赖关系等问题。如果图中存在环，那么环中的每个顶点都应该排在其他顶点之前，这是不可能的，因为环中的顶点之间存在相互依赖关系。例如，对于环A->B->C->A，A应该排在B之前，B应该排在C之前，而C应该排在A之前，这是矛盾的。因此，存在环的有向图不能进行拓扑排序。在实现拓扑排序算法时，通常需要检测图中是否存在环。如果算法结束时仍有顶点未被访问，则说明图中存在环。5.答案：每一步都做出当前看起来最优的选择；问题的最优解包含其子问题的最优解解释：在贪心算法中，贪心选择性质是指每一步都做出当前看起来最优的选择，希望通过一系列的局部最优选择达到全局最优。例如，在活动选择问题中，每一步都选择结束时间最早的活动，这样可以尽可能多地安排活动。最优子结构性质是指问题的最优解包含其子问题的最优解。这意味着我们可以通过求解子问题的最优解来构建原问题的最优解。例如，在活动选择问题中，如果已经选择了某个活动，那么剩下的活动选择问题也是一个活动选择问题，且可以独立求解。贪心算法的正确性依赖于贪心选择性质和最优子结构性质。如果问题不满足这两个性质，贪心算法可能无法得到全局最优解。例如，在背包问题中，如果每一步都选择价值密度最高的物品，可能无法得到最优解。三、判断题（共10分）1.答案：正确解释：在平衡二叉搜索树（如AVL树）中，任何节点的两个子树的高度差（平衡因子）不超过1。这一性质保证了AVL树的高度保持在O(logn)，从而保证了查找、插入和删除操作的时间复杂度为O(logn)。当在AVL树中进行插入或删除操作时，可能会导致某些节点的平衡因子超过1，此时需要进行旋转操作来恢复平衡。AVL树有四种旋转操作：左旋、右旋、左右旋和右左旋。例如，对于不平衡的节点，如果其左子树比右子树高2，且左子节点的左子树比右子树高，则需要进行右旋操作；如果左子节点的右子树比左子树高，则需要进行左右旋操作。AVL树的优点是保证了操作的平衡时间复杂度，缺点是旋转操作会增加额外的开销。2.答案：正确解释：在B树中，所有叶子节点都位于同一层。这一性质保证了B树的高度平衡，从而保证了高效的查找操作。B树的这一特性使其特别适合用于磁盘存储系统，因为可以减少磁盘I/O操作次数。B树是一种多路搜索树，每个节点可以有多个子节点。B树的节点通常包含关键字和指向子节点的指针。关键字按非递减顺序排列，每个关键字对应一个子树，该子树中的所有关键字都介于该关键字和前一个关键字之间（对于第一个关键字，对应子树中的关键字都小于该关键字）。B树的阶数是指每个节点最多包含的关键字数。例如，一个m阶B树的每个节点最多包含m-1个关键字和m个子节点。B树的插入和删除操作需要保持B树的性质，包括所有叶子节点位于同一层、每个节点包含的关键字数在[m/2]-1到m-1之间等。如果违反这些性质，需要进行分裂或合并操作。3.答案：正确解释：使用邻接矩阵存储图时，需要为每个可能的边（包括不存在的边）分配空间，因此空间复杂度为O(V^2)，其中V是顶点数。这种表示方法适合于稠密图，即边数接近V^2的图。邻接矩阵是一个二维数组，matrix[i][j]表示顶点i和顶点j之间的边。对于无向图，邻接矩阵是对称的；对于有向图，邻接矩阵不一定对称。邻接矩阵的优点是可以快速判断两个顶点之间是否存在边（O(1)时间），以及可以方便地计算每个顶点的度（对于无向图，度是对应行或列中1的个数；对于有向图，出度是对应行中1的个数，入度是对应列中1的个数）。缺点是空间复杂度高，不适合存储稀疏图。对于稀疏图，通常使用邻接表存储，空间复杂度为O(V+E)，其中E是边数。4.答案：错误解释：在并查集中，路径压缩和按秩合并可以将操作的时间复杂度降低到接近O(α(n))，其中α(n)是阿克曼函数的反函数，增长极其缓慢，可以视为常数。但并不是严格的O(1)时间复杂度。并查集是一种用于处理不相交集合的数据结构，主要支持两种操作：find（查找元素所属的集合）和union（合并两个集合）。路径压缩是在find操作中，将查找路径上的所有节点直接指向根节点，从而缩短查找路径。按秩合并是在union操作中，将深度较小的树合并到深度较大的树下，从而保持树的高度平衡。虽然路径压缩和按秩合并可以将操作的时间复杂度降低到接近O(1)，但并不是严格的O(1)时间复杂度。阿克曼函数的反函数α(n)增长极其缓慢，对于实际应用中的n值，α(n)的值不超过5，因此可以视为常数。5.答案：错误解释：虽然动态规划要求问题满足最优子结构性质，但仅仅满足最优子结构性质并不足以使用动态规划解决问题。动态规划还要求问题满足重叠子问题的性质，即相同的子问题被多次求解。最优子结构性质是指问题的最优解包含其子问题的最优解。例如，在背包问题中，物品的最优装载方案包含了前n-1个物品的最优装载方案。重叠子问题性质是指在递归求解过程中，相同的子问题被多次求解。例如，在计算斐波那契数列时，fib(n)=fib(n-1)+fib(n-2)，而fib(n-1)和fib(n-2)又会递归地计算fib(n-2)和fib(n-3)，导致fib(n-2)被计算两次。如果问题只满足最优子结构性质，但不满足重叠子问题性质，使用动态规划可能会导致重复计算，效率低下。例如，对于二叉树的最大独立集问题，虽然满足最优子结构性质，但不满足重叠子问题性质，因此不适合使用动态规划解决。四、简答题（共20分）1.分治算法是一种将问题分解为更小的子问题，递归地解决子问题，然后将子问题的解合并为原问题的解的算法策略。分治算法的三个步骤是：a)分解（Divide）：将原问题分解为若干个规模较小的子问题，这些子问题与原问题形式相同，但规模更小。例如，在归并排序中，将数组分为两个子数组；在矩阵乘法中，将矩阵分为四个子矩阵。b)解决（Conquer）：递归地解决各个子问题。如果子问题的规模足够小，则直接求解。例如，在归并排序中，当子数组的大小为1时，认为已经有序；在矩阵乘法中，当子矩阵的大小为1时，直接计算元素乘积。c)合并（Combine）：将子问题的解合并为原问题的解。例如，在归并排序中，将两个有序的子数组合并为一个有序的数组；在矩阵乘法中，将四个子矩阵的乘积组合为原矩阵的乘积。分治算法在解决以下类型的问题时特别有效：-可以分解为独立子问题的问题：如归并排序、快速排序等。在这些算法中，子问题之间相互独立，可以独立求解。-子问题规模较小，可以直接求解的问题：如矩阵乘法、Strassen算法等。在这些算法中，当子问题的规模小于某个阈值时，可以直接求解，避免递归带来的开销。-子问题解的合并过程相对简单的问题：如最近点对问题、凸包问题等。在这些算法中，合并子问题的解的过程相对简单，不会显著增加算法的复杂度。分治算法的优点是可以将复杂问题分解为简单问题，降低问题的复杂度；缺点是递归可能导致较高的空间复杂度，且合并过程可能复杂。此外，分治算法通常需要问题的子问题相互独立，否则可能无法直接应用分治策略。2.回溯算法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化来丢弃该解，即"回溯"到上一步，尝试别的候选解。回溯算法的基本框架如下：a)定义问题的解空间：确定问题所有可能的解。例如，在八皇后问题中，解空间是所有可能的皇后放置方案；在子集和问题中，解空间是所有可能的子集。b)组织解空间：使用树或图等数据结构组织解空间。例如，在八皇后问题中，可以使用一棵树表示，每个节点代表一个皇后的放置位置；在子集和问题中，可以使用一棵二叉树表示，每个节点代表是否选择某个元素。c)搜索解空间：使用深度优先搜索策略遍历解空间，在搜索过程中：-如果当前解是可行解，则将其加入解集；-如果当前解不满足约束条件，则回溯到上一步；-如果当前解是部分解，则继续扩展。例如，在八皇后问题中，从第一行开始，逐行放置皇后，每次放置时检查是否与已放置的皇后冲突。如果冲突，则回溯到上一行，尝试下一个位置；如果不冲突，则继续放置下一行的皇后。当所有行都放置了皇后，得到一个可行解。回溯算法与动态规划的区别主要体现在以下几个方面：-解的性质：回溯算法通常用于找出所有解或最优解，而动态规划通常用于计算最优值。例如，在背包问题中，回溯算法可以找出所有可能的装载方案，而动态规划通常用于计算最大价值。-子问题重叠性：动态规划依赖于子问题的重叠性，通过存储子问题的解避免重复计算；回溯算法则不依赖于子问题的重叠性，而是通过剪枝来减少搜索空间。-空间复杂度：动态规划通常需要存储子问题的解，空间复杂度较高；回溯算法的空间复杂度通常较低，只需要存储当前解和搜索路径。-适用问题：回溯算法适用于组合优化问题、排列组合问题等，如八皇后问题、子集和问题、旅行商问题等；动态规划适用于具有重叠子问题和最优子结构的问题，如背包问题、最长公共子序列问题、矩阵连乘问题等。五、编程题（共30分）1.解答：要解决这个问题，我们可以使用哈希表（字典）来存储数组中每个元素的值和其对应的索引。遍历数组，对于每个元素，检查是否存在另一个元素等于target减去当前元素。如果存在，则返回这两个元素的索引。这种方法的时间复杂度为O(n)，其中n是数组的长度，因为只需要遍历数组一次。空间复杂度为O(n)，因为需要使用哈希表存储数组中的元素及其索引。以下是Python实现代码：```pythondeftwoSum(nums,target):num_dict={}fori,numinenumerate(nums):complement=target-numifcomplementinnum_dict:return[num_dict[complement],i]num_dict[num]=ireturn[]```代码解释：-创建一个空字典num_dict，用于存储数组中的元素及其索引。-遍历数组，对于每个元素num：-计算complement=target-num。-检查complement是否在num_dict中，如果在，说明已经找到了两个数的和等于target，返回它们的索引[num_dict[complement],i]。-如果complement不在num_dict中，将当前元素num及其索引i存入num_dict。-如果遍历完整个数组都没有找到符合条件的两个数，返回空列表。示例：对于输入nums=[2,7,11,15]，target=9，函数的执行过程如下：-初始化num_dict={}。-遍历nums[0]=2：-complement=9-2=7。-7不在num_dict中，将2存入num_dict，num_dict={2:0}。-遍历nums[1]=7：-complement=9-7=2。-2在num_dict中，返回[num_dict[2],1]=[0,1]。因此，函数返回[0,1]。另一种方法是先对数组进行排序，然后使用双指针法。这种方法的时间复杂度为O(nlogn)，空间复杂度为O(1)（如果忽略排序的空间复杂度）。以下是Python实现代码：```pythondeftwoSum(nums,target):创建一个包含值和原始索引的列表nums_with_index=[(num,i)fori,numinenumerate(nums)]按值排序nums_with_index.sort()初始化双指针left,right=0,len(nums_with_index)-1whileleft<right:current_sum=nums_with_index[left][0]+nums_with_index[right][0]ifcurrent_sum==target:return[nums_with_index[left][1],nums_with_index[right][1]]elifcurrent_sum<target:left+=1else:right-=1return[]```代码解释：-创建一个包含值和原始索引的列表nums_with_index。-对nums_with_index按值排序。-初始化双指针left和right，分别指向数组的开头和结尾。-在循环中，计算当前两个指针所指元素的和：-如果和等于target，返回这两个元素的原始索引。-如果和小于target，将左指针右移，增大和。-如果和大于target，将右指针左移，减小和。-如果循环结束仍未找到符合条件的两个数，返回空列表。这种方法的时间复杂度主要取决于排序的时间复杂度O(nlogn)，双指针遍历的时间复杂度为O(n)。空间复杂度为O(n)，因为需要存储值和原始索引的列表。2.解答：要解决这个问题，我们可以使用滑动窗口技术。滑动窗口是一种双指针技术，用于解决数组或字符串的子数组或子串问题。在这个问题中，我们需要找到一个不含有重复字符的最长子串。滑动窗口的基本思想是维护一个窗口，窗口内的字符都是唯一的。使用两个指针left和right表示窗口的左右边界，初始时left=0，right=0。然后移动right指针，将字符加入窗口，如果遇到重复字符，则移动left指针，直到窗口内不再有重复字符。这种方法的时间复杂度为O(n)，其中n是字符串的长度，因为每个字符最多被访问两次（一次由right指针，一次由left指针）。空间复杂度为O(min(m,n))，其中m是字符集的大小，因为集合中最多存储m个字符。以下是Python实现代码：```pythondeflengthOfLongestSubstring(s):char_set=set()left=0max_length=0forrightinrange(len(s)):whiles[right]inchar_set:char_set.remove(s[left])left+=1char_set.add(s[right])max_length=max(max_length,right-left+1)returnmax_length```代码解释：-创建一个集合char_set，用于存储当前窗口中的字符。-初始化左指针left为0，最大长度max_length为0。-遍历字符串，右指针right从0到字符串末尾：-如果当前字符s[right]已经在char_set中，说明窗口中存在重复字符，需要移动左指针left，直到窗口中不再包含重复字符。-将当前字符s[right]添加到char_set中。-更新最大长度max_length为当前窗口长度（right-left+1）和max_length中的较大值。-返回最大长度max_length。示例：对于输入s="abcabcbb"，函数的执行过程如下：-初始化char_set={}，left=0，max_length=0。-right=0，s[0]='a'：-'a'不在char_set中，char_set={'a'}，max_length=max(0,0-0+1)=1。-right=1，s[1]='b'：-'b'不在char_set中，char_set={'a','b'}，max_length=max(1,1-0+1)=2。-right=2，s[2]='c'：-'c'不在char_set中，char_set={'a','b','c'}，max_length=max(2,2-0+1)=3。-right=3，s[3]='a'：-'a'在char_set中，移动left指针：-移除s[0]='a'，char_set={'b','c'}，left=1。-'a'不在char_set中，char_set={'b','c','a'}，max_length=max(3,3-1+1)=3。-right=4，s[4]='b'：-'b'在char_set中，移动left指针：-移除s[1]='b'，char_set={'c','a'}，left=2。-'b'不在char_set中，char_set={'c','a','b'}，max_length=max(3,4-2+1)=3。-right=5，s[5]='c'：-'c'在char_set中，移动left指针：-移除s[2]='c'，char_set={'a','b'}，left=3。-'c'不在char_set中，char_set={'a','b','c'}，max_length=max(3,5-3+1)=3。-right=6，s[6]='b'