LeetCode 1695. 删除子数组的最大得分 —— 学习笔记 一、 题目核心解析题目要求从一个正整数数组nums中找出一个连续的子数组。限定条件子数组内不能有重复的数字所有元素独一无二。该子数组的元素之和得分要最大。核心思路求连续片段的问题通常优先考虑使用滑动窗口Sliding Window算法避免暴力双重循环导致的超时。️ 二、 核心算法滑动窗口双指针滑动窗口就像一个可以伸缩的“长方形框子”我们在数组上维持这个框子right右指针负责探索新世界。它不断向右移动把新数字拉进窗口。left左指针负责清理门户。一旦发现新拉进来的数字和窗口里的数字重复了left就必须向右移动直到把重复的那个旧数字踢出窗口。 三、 C 关键工具箱std::unordered_set在这道题中我们需要极快地判断一个数字“在不在当前的窗口里”。C 的哈希集合std::unordered_setint是最佳选择。 常用语法笔记操作错误写法类似 Map正确集合语法作用检查是否存在if (seen[x])❌seen.count(x)✅返回 1 代表存在0 代表不存在加入集合seen[x]❌seen.insert(x)✅将元素x放入登记表移出集合无 ❌seen.erase(x)✅将元素x从登记表中删除⚠️注意unordered_set是一个只记录“有没有”的集合不支持[]下标操作和、--运算。 四、 避坑指南易错点盘点1. 为什么必须用while而不是if在发现新数字重复时我们必须使用while (seen.count(nums[right]))。原因如果使用if左指针left只会向右移动一步。如果重复的数字在窗口靠后的位置移动一步并不能消除重复此时强行加入新数字就会破坏“无重复”的规则。使用while可以让left一直向右退直到窗口内彻底没有这个重复数字为止。2. 移除元素时的“三步走”当窗口缩小left右移时必须同时更新三个状态current_sum-nums[left];// 1. 从当前总和中扣除seen.erase(nums[left]);// 2. 从哈希表中注销left;// 3. 左指针右移 五、 最终代码逻辑结构完整的标准解题逻辑如下你可以以此作为最终编写代码的参考classSolution{public:intmaximumUniqueSubarray(vectorintnums){unordered_setintseen;// 登记表记录当前窗口内的数字intcurrent_sum0;// 记录当前窗口内数字的总和intmax_sum0;// 记录历史最高得分intleft0;// 左指针// 右指针遍历整个数组for(intright0;rightnums.size();right){// 1. 发现重复左指针持续收缩窗口直到重复数字被踢出while(seen.count(nums[right])){current_sum-nums[left];seen.erase(nums[left]);left;}// 2. 将新数字安全地加入窗口seen.insert(nums[right]);current_sumnums[right];// 3. 每次窗口稳定后更新最大得分max_summax(max_sum,current_sum);}returnmax_sum;}};