LeetCode-Go 题解：1695. Maximum Erasure Value —— 滑动窗口求解“元素互不重复的最大子数组和“

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[l+1], ..., a[r]，则b是a的子数组。这意味着我们要找的窗口必须是连续的，这一点是滑动窗口（而非子序列 DP）成立的先决条件。

两个官方示例

示例 1：

Input: 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]，和为2+4+5+6 = 17。

示例 2：

Input: 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^5
• 1 <= nums[i] <= 10^4

约束中nums[i] >= 1保证了元素和单调递增，这使"窗口越大越好（在无重复的前提下）"的贪心直觉成立；nums[i] <= 10^4则保证了用 map 统计频次时键空间有限。

二、解题思路：滑动窗口 + 频次统计

题解文档给出的核心思路（原文）：

读完题立马能识别出这是经典的滑动窗口题。利用滑动窗口从左往右滑动窗口，滑动过程中统计频次，如果是不同元素，右边界窗口右移，否则左边窗口缩小。每次移动更新 max 值。最终扫完一遍以后，max 值即为所求。

拆解为三个不变量的维护：

1. 窗口合法性：当前窗口[left, right]内任意时刻都保持"元素互不重复"，通过频次表freq判定；
2. 右边界扩张：若nums[right+1]的频次为 0（即与窗口内所有元素都不重复），则把它纳入窗口，right++；
3. 左边界收缩：若下一个元素与窗口内元素重复，则从窗口左侧不断弹出元素（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 right+1 < len(nums) && freq[nums[right+1]] == 0 { freq[nums[right+1]]++ 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：窗口左边界，初始为 0；
• right：窗口右边界，初始为-1，表示窗口为空，与后文right+1的扩张逻辑配套；
• freq：频次表，freq[v]记录元素v在当前窗口内出现的次数。

入口处if len(nums) == 0 { return 0 }对空数组做了防御性处理，这与 测试用例 中para1695{[]int{}} -> 0的用例一一对应。

3.2 窗口扩张 / 收缩的分支逻辑

if right+1 < len(nums) && freq[nums[right+1]] == 0 { freq[nums[right+1]]++ right++ } else { freq[nums[left]]-- left++ }

这一分支是本算法的灵魂：

• 扩张分支：right+1 < len(nums)保证不越界，freq[nums[right+1]] == 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，累计求和代价为1+2+...+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 }

测试用例覆盖三个场景：

运行测试：

# 单个题目包 go test -v ./leetcode/1695.Maximum-Erasure-Value/ -run Test_Problem1695 # 全仓库（生成覆盖率文件，对应 gotest.sh 中的脚本） go test -covermode=atomic -coverprofile=coverage.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