LeetCode-Go 题解1695. Maximum Erasure Value —— 滑动窗口求解元素互不重复的最大子数组和【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读1695. Maximum Erasure Value 是一道经典的滑动窗口Sliding Window入门题在正整数数组中恰好删除一段元素互不重复的连续子数组使该子数组的元素和最大。本文以 LeetCode-Go 仓库中该题的 题解文档 为骨架结合 Go 源码实现 与 测试用例逐行拆解滑动窗口 频次统计freq map的实现原理、时间复杂度边界与工程化验证方式。读完本文你将掌握固定窗口语义 动态收缩这一类去重子数组问题的通用解法模板。一、题目解析删除一段无重复元素的子数组题目原文见 题解文档You are given an array of positive integersnumsand want to erase a subarray containingunique elements. Thescoreyou get by erasing the subarray is equal to thesumof its elements. Returnthemaximum scoreyou can get by erasingexactly onesubarray.翻译成中文即给你一个正整数数组nums请你从中删除一个含有若干不同元素的子数组即子数组内所有元素互不重复删除子数组的得分就是子数组各元素之和返回只删除一个子数组可获得的最大得分。子数组subarray定义为数组a的一个连续子序列若存在(l, r)使得b a[l], a[l1], ..., a[r]则b是a的子数组。这意味着我们要找的窗口必须是连续的这一点是滑动窗口而非子序列 DP成立的先决条件。两个官方示例示例 1Input: nums [4,2,4,5,6] Output: 17 Explanation: The optimal subarray here is [2,4,5,6].数组中有重复元素4。若窗口覆盖两个4则违反元素互不重复约束因此最优解是跳过其中一个4取[2,4,5,6]和为2456 17。示例 2Input: nums [5,2,1,2,5,2,1,2,5] Output: 8 Explanation: The optimal subarray here is [5,2,1] or [1,2,5].多个候选窗口并列最优[5,2,1]或[1,2,5]和均为8。数据范围约束1 nums.length 10^51 nums[i] 10^4约束中nums[i] 1保证了元素和单调递增这使窗口越大越好在无重复的前提下的贪心直觉成立nums[i] 10^4则保证了用 map 统计频次时键空间有限。二、解题思路滑动窗口 频次统计题解文档给出的核心思路原文读完题立马能识别出这是经典的滑动窗口题。利用滑动窗口从左往右滑动窗口滑动过程中统计频次如果是不同元素右边界窗口右移否则左边窗口缩小。每次移动更新 max 值。最终扫完一遍以后max 值即为所求。拆解为三个不变量的维护窗口合法性当前窗口[left, right]内任意时刻都保持元素互不重复通过频次表freq判定右边界扩张若nums[right1]的频次为 0即与窗口内所有元素都不重复则把它纳入窗口right左边界收缩若下一个元素与窗口内元素重复则从窗口左侧不断弹出元素freq[nums[left]]--; left直到窗口重新合法再继续尝试扩张。每次窗口状态变化后计算当前窗口内元素和并与历史最大值比较最终全局最大值即为答案。整个过程只需线性遍历天然适配连续子数组 无重复约束这类问题。三、源码逐行拆解Go 实现与关键细节仓库中 1695. Maximum Erasure Value.go 的完整实现如下package leetcode func maximumUniqueSubarray(nums []int) int { if len(nums) 0 { return 0 } result, left, right, freq : 0, 0, -1, map[int]int{} for left len(nums) { if right1 len(nums) freq[nums[right1]] 0 { freq[nums[right1]] right } else { freq[nums[left]]-- left } sum : 0 for i : left; i right; i { sum nums[i] } result max(result, sum) } return result } func max(a int, b int) int { if a b { return a } return b }3.1 状态变量的初始化result, left, right, freq : 0, 0, -1, map[int]int{}result全局最大得分初始为 0空数组场景兜底left窗口左边界初始为 0right窗口右边界初始为-1表示窗口为空与后文right1的扩张逻辑配套freq频次表freq[v]记录元素v在当前窗口内出现的次数。入口处if len(nums) 0 { return 0 }对空数组做了防御性处理这与 测试用例 中para1695{[]int{}} - 0的用例一一对应。3.2 窗口扩张 / 收缩的分支逻辑if right1 len(nums) freq[nums[right1]] 0 { freq[nums[right1]] right } else { freq[nums[left]]-- left }这一分支是本算法的灵魂扩张分支right1 len(nums)保证不越界freq[nums[right1]] 0保证待加入元素与窗口内所有元素不重复。满足条件则将其频次 1 并右移右边界窗口保持无重复收缩分支否则说明要么右边界已到数组尽头要么下一个元素与窗口内元素重复。此时把左边界元素从窗口弹出频次 -1、left窗口缩小后重新进入循环判断直到可以继续扩张。循环退出条件为left len(nums)当左边界扫过整个数组后所有可能的合法窗口均已枚举完毕。3.3 窗口求和与最大值更新sum : 0 for i : left; i right; i { sum nums[i] } result max(result, sum)每次窗口状态变化后重新累加[left, right]区间内的元素和并用自定义的max辅助函数更新全局最大值。需要特别说明的复杂度边界从源码结构推断此处每次窗口移动都重新遍历窗口求和而非增量维护窗口和。在最坏情况如数组元素全部互异下右边界持续扩张、窗口长度依次为1, 2, ..., n累计求和代价为12...n O(n²)。因此从源码结构看该实现最坏时间复杂度为 O(n²)平均情况接近 O(n)空间复杂度为 O(n)频次表。若要严格达到 O(n)可将窗口求和改造为增量维护扩张时sum nums[right]收缩时sum - nums[left]代码更短且效率更稳。3.4 关于max辅助函数实现中手写了max(a, b int) int而非直接使用标准库。仓库 go.mod 声明的 Go 版本为go 1.19而math.Max针对 float 类型builtin.max泛型内建函数在 Go 1.21 才引入因此手写max是兼容旧版本 Go 的稳妥做法也符合 LeetCode 在线评测环境的通用写法。四、测试用例验证仓库级质量保障LeetCode-Go 仓库以100% test coverage为工程目标1695. Maximum Erasure Value_test.go 采用统一的question1695 / para1695 / ans1695结构组织用例type question1695 struct { para1695 ans1695 } type para1695 struct { nums []int } type ans1695 struct { one int }测试用例覆盖三个场景输入nums期望输出说明[4,2,4,5,6]17官方示例 1最优窗口[2,4,5,6][5,2,1,2,5,2,1,2,5]8官方示例 2多个并列最优窗口[]0空数组边界场景对应源码的防御性判断运行测试# 单个题目包 go test -v ./leetcode/1695.Maximum-Erasure-Value/ -run Test_Problem1695 # 全仓库生成覆盖率文件对应 gotest.sh 中的脚本 go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...其中第二条命令对应仓库根目录 gotest.sh 的核心逻辑——一次性对./leetcode/...下所有包生成单一合法的覆盖率文件coverage.txt这是 LeetCode-Go 保持100% test coverage声明可验证的工程基础。五、算法变体与举一反三滑动窗口这一技巧在 LeetCode-Go 仓库的 README_zh.md 中被单列为 ✅ 已完成的专题Sliding Window。与 1695 同源的经典变体包括求最大长度把求最大和换成求最长无重复子串长度如 3. Longest Substring Without Repeating Characters此时窗口内维护的是字符频次状态更新逻辑与本题完全同构求最小窗口当约束变成至少包含某种条件时滑动方向与收缩触发条件互换但扩张 收缩 维护合法窗口的三段式框架不变固定窗口大小如子数组最大平均值类问题窗口按固定步长滑动无需频次收缩逻辑。掌握本题的频次表判定 双指针维护合法窗口模型后面对连续子数组 去重/覆盖/出现次数类题目都可以先尝试用同一套模板建立合法窗口的不变量再针对求和 or 求长 or 求短定制更新逻辑。六、总结LeetCode-Go 对 1695 题的解法提供了一个教科书级的滑动窗口模板以freq频次表维护窗口内元素互不重复的不变量右边界贪心扩张、左边界按需收缩每次状态变化后更新全局最优。配合仓库内 题解文档、实现源码 与 测试用例 三者对照阅读即可完整复现从识别题型到编码验证的全流程。若追求严格的 O(n) 上界只需将窗口求和改为增量维护其余逻辑保持不变。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考