1695.删除子数组的最大得分：滑动窗口(哈希表)

【LetMeFly】1695.删除子数组的最大得分：滑动窗口(哈希表)

力扣题目链接：https://leetcode.cn/problems/maximum-erasure-value/

给你一个正整数数组 nums ，请你从中删除一个含有 若干不同元素 的子数组。删除子数组的 得分 就是子数组各元素之 和 。

返回 只删除一个 子数组可获得的 最大得分 。

如果数组 b 是数组 a 的一个连续子序列，即如果它等于 a[l],a[l+1],...,a[r] ，那么它就是 a 的一个子数组。

 

示例 1：

输入：nums = [4,2,4,5,6]
输出：17
解释：最优子数组是 [2,4,5,6]

示例 2：

输入：nums = [5,2,1,2,5,2,1,2,5]
输出：8
解释：最优子数组是 [5,2,1] 或 [1,2,5]

 

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 104

解题方法：滑动窗口

这道题翻译一下就是：找和最大的不包含相同元素的子数组。

怎么找？滑动窗口即可。

使用两个指针指向窗口的两个端点，窗口范围内的数组为以右指针r为终点的最长的子数组。

每次右指针右移一位，如果窗口中已经包含了要新加入的元素，就将左指针不断左移，直到窗口中不包含右指针指向的新元素为止。

如何快速判断窗口中一个元素是否已经存在？使用一个哈希表统计即可。

• 时间复杂度$O(len(nums))$，左右指针每个元素各自最多遍历一次。
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-07-23 10:31:42
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-07-23 13:26:19
 */
#if defined(_WIN32) || defined(__APPLE__)
#include "_[1,2]toVector.h"
#endif

class Solution {
public:
    int maximumUniqueSubarray(vector<int>& nums) {
        unordered_set<int> had;
        int ans = 0, cnt = 0;
        for (int l = 0, r = 0; r < nums.size(); r++) {
            while (had.count(nums[r])) {
                had.erase(nums[l]);
                cnt -= nums[l++];
            }
            had.insert(nums[r]);
            cnt += nums[r];
            // printf("l = %d, r = %d, cnt = %d\n", l, r, cnt);
            ans = max(ans, cnt);
        }
        return ans;
    }
};

/*
[187,470,25,436,538,809,441,167,477,110,275,133,666,345,411,459,490,266,987,965,429,166,809,340,467,318,125,165,809,610,31,585,970,306,42,189,169,743,78,810,70,382,367,490,787,670,476,278,775,673,299,19,893,817,971,458,409,886,434]
9252
16911
*/

Python

'''
Author: LetMeFly
Date: 2025-07-23 10:31:42
LastEditors: LetMeFly.xyz
LastEditTime: 2025-07-23 13:29:36
'''
from typing import List

class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        had = set()
        ans = l = cnt = 0
        for v in nums:
            while v in had:
                had.remove(nums[l])
                cnt -= nums[l]
                l += 1
            had.add(v)
            cnt += v
            ans = max(ans, cnt)
        return ans

Java

/*
 * @Author: LetMeFly
 * @Date: 2025-07-23 10:31:42
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-07-24 13:22:02
 */
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int maximumUniqueSubarray(int[] nums) {
        int ans = 0;
        Set<Integer> had = new HashSet<>();
        for (int l = 0, r = 0, cnt = 0; r < nums.length; r++) {
            while (had.contains(nums[r])) {
                had.remove(nums[l]);
                cnt -= nums[l++];
            }
            had.add(nums[r]);
            cnt += nums[r];
            ans = Math.max(ans, cnt);
        }
        return ans;
    }
}

Go

/*
 * @Author: LetMeFly
 * @Date: 2025-07-23 10:31:42
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-07-24 13:16:17
 */
package main

// import "fmt"

func maximumUniqueSubarray(nums []int) (ans int) {
    had := map[int]struct{}{}
    l, cnt := 0, 0
    for _, t := range nums {
        for _, ok := had[t]; ok; _, ok = had[t] {
            delete(had, nums[l])
            cnt -= nums[l]
            l++
        }
        cnt += t
        had[t] = struct{}{}
        ans = max(ans, cnt)
    }
    return
}

// func main() {
//     nums := []int{4, 2, 4, 5, 6}
//     ans := maximumUniqueSubarray(nums)
//     fmt.Println(ans)
// }

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源

今天发现CSDN文章的代码块还带“运行”按钮了。