Medium

题目描述

给你一个正整数数组 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 <= 10^5
  • 1 <= nums[i] <= 10^4

解题思路

这道题要求找到包含唯一元素的子数组的最大和。关键在于理解"唯一元素"指的是子数组中不能有重复元素。

解题思路：

这是一个典型的滑动窗口问题。我们需要维护一个窗口，使得窗口内的所有元素都不重复，并且要最大化窗口内元素的和。

使用双指针技术：

  1. 维护左右两个指针 left 和 right，以及一个哈希集合来记录当前窗口中的元素
  2. 右指针不断向右扩展窗口，将新元素加入窗口和集合中
  3. 当遇到重复元素时，左指针向右移动直到移除重复元素
  4. 在这个过程中，记录遇到的最大窗口和

算法步骤：

  • 初始化左指针、当前窗口和、最大和
  • 使用哈希集合记录当前窗口中的元素
  • 遍历数组，对于每个右指针位置：
    • 如果当前元素不在集合中，直接加入
    • 如果当前元素在集合中，移动左指针直到移除重复元素
    • 更新当前窗口和，并记录最大值

时间复杂度为 O(n)，因为每个元素最多被访问两次（一次加入，一次移除）。

代码实现

class Solution {
public:
    int maximumUniqueSubarray(vector<int>& nums) {
        unordered_set<int> seen;
        int left = 0, maxSum = 0, currentSum = 0;
        
        for (int right = 0; right < nums.size(); right++) {
            while (seen.count(nums[right])) {
                seen.erase(nums[left]);
                currentSum -= nums[left];
                left++;
            }
            
            seen.insert(nums[right]);
            currentSum += nums[right];
            maxSum = max(maxSum, currentSum);
        }
        
        return maxSum;
    }
};

class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        seen = set()
        left = 0
        max_sum = 0
        current_sum = 0
        
        for right in range(len(nums)):
            while nums[right] in seen:
                seen.remove(nums[left])
                current_sum -= nums[left]
                left += 1
            
            seen.add(nums[right])
            current_sum += nums[right]
            max_sum = max(max_sum, current_sum)
        
        return max_sum

public class Solution {
    public int MaximumUniqueSubarray(int[] nums) {
        HashSet<int> seen = new HashSet<int>();
        int left = 0, maxSum = 0, currentSum = 0;
        
        for (int right = 0; right < nums.Length; right++) {
            while (seen.Contains(nums[right])) {
                seen.Remove(nums[left]);
                currentSum -= nums[left];
                left++;
            }
            
            seen.Add(nums[right]);
            currentSum += nums[right];
            maxSum = Math.Max(maxSum, currentSum);
        }
        
        return maxSum;
    }
}

var maximumUniqueSubarray = function(nums) {
    const seen = new Set();
    let left = 0, maxSum = 0, currentSum = 0;
    
    for (let right = 0; right < nums.length; right++) {
        while (seen.has(nums[right])) {
            seen.delete(nums[left]);
            currentSum -= nums[left];
            left++;
        }
        
        seen.add(nums[right]);
        currentSum += nums[right];
        maxSum = Math.max(maxSum, currentSum);
    }
    
    return maxSum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n) - 每个元素最多被访问两次
空间复杂度O(min(n, k)) - 其中k是元素的不同值个数，最坏情况下为O(n)

相关题目