Leetcode小白试炼(20201221 删除子数组的最大得分)_mar..._CSDN博客

来自 : CSDN技术社区 发布时间：2021-03-25

2. 示例

示例 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]

3. 题目解析

要求找到一个没有重复元素的总和最大的连续子序列 数据量大 要考虑如何避免超时。

二、个人解法 1. 解法分析

要解决的问题主要有三个

确定子序列起始下标 确定符合条件“无重复元素”的最大结束下标。所有符合条件的子序列中选出总和最大的子序列 返回最大值。

分别针对三个问题的解决

遍历数组 依次选取当前遍历的元素作为子序列起始下标 使用HashMap或Set 找见符合条件“无重复元素”的最大结束下标 使用变量sum记录子序列的和 然后使用全局变量result来记录所有子序列的和的最大值。 2. 代码

public int maximumUniqueSubarray(int[] nums) { HashMap Integer, Integer map new HashMap (); int start 0; int sum 0; int max 0; while (start nums.length) { for (int i start; i nums.length; i ) { map.put(nums[i], map.getOrDefault(nums[i], 0) 1); if (map.get(nums[i]) 1) { break; else { sum nums[i]; max Math.max(max,sum); sum 0; start ; map.clear(); return max;

3. 失败反思

超时 时间复杂度太高。

4. 改进 改进点

分析实例
数组nums [5,2,1,2,5,2,1,2,5]
第一个子序列的起始为下标0 到下标为3的时候出现重复元素2 子序列结束。此时若将下标1作为第二个子序列的起始下标 那么还是在下标2的地方结束子序列。第二个子序列是第一个子序列的子序列 总和会变得更小 浪费了我们的搜索时间。
如图所示 子序列2没有必要搜索遍历。

基于此 对要解决的问题1进行改进
在找子序列的结束下标时 用HashMap的value记录子序列中的每一个元素的下标 在子序列A遇到重复元素s的时候 A序列结束。下一个子序列B的起始下标 就是子序列A中记录的这个重复元素s的value 1。
如图所示 使用改进后的方式可以减少遍历时间。

代码

import java.util.HashMap;import java.util.HashSet;public class Zhou1 {public int maximumUniqueSubarray(int[] nums) {HashMap Integer, Integer map new HashMap ();// HashSet Integer set new HashSet ();int start 0;int sum 0;int max 0;while (start nums.length) {for (int i start; i nums.length; i ) {if (map.containsKey(nums[i])) {//获取下一个子序列起始坐标start map.get(nums[i]) 1;break;} else {map.put(nums[i], i);sum nums[i];if (i nums.length - 1)return Math.max(sum, max);max Math.max(max, sum);sum 0;map.clear();return max;public int maximumUniqueSubarray1(int[] nums) {HashSet Integer set new HashSet ();int sum 0;for (int i 0; i nums.length; i ) {if (set.add(nums[i])) {sum nums[i];return sum;

5. 再次失败反思

改进后的算法 减少了产生的子序列个数 但是还有两个耗费时间的关键点
1.每个子序列都进行了元素累加 这些重复计算耗费时间。
2.每个子序列都要初始化一次哈希表或者集合 重新往集合内添加元素 这也非常耗费时间。

三、官网高星解法 1. 双指针集合法 1 解法分析

针对二个耗费时间点进行了改进

初始化两个指针start end 0 最大值变量result 实例化一个集合备用。往集合内添加元素 同时对添加的元素进行累计求和 并移动end指针 直到遇到重复元素 代表一个子序列产生 求和结果与result取最大值存至result 此时end指向遇到的重复元素。利用while循环 左移指针start 直至start指针越过与end指针值相同的元素 此时end指针指向的元素可以正常添加至集合 遍历继续。知道再遇到下一个重复元素 结束当前子序列。在这个过程中 左指针移动的时候 集合的总和要减去start指向的元素 右指针移动的时候 集合的总和要加上end指向的元素。

优点
这样可以避免每次寻找新的子序列都要清空集合容器重新添加元素 也可以减少累加操作 但是增加了少量的减法操作。

2 代码

 public int maximumUniqueSubarray(int[] nums) { int res 0,sum 0; Set Integer set new HashSet (); int left 0,right 0; for(right 0;right nums.length;right ){ while(set.contains(nums[right])){ set.remove(nums[left]); sum- nums[left ]; set.add(nums[right]); sum nums[right]; res Math.max(res,sum); return res;

3 算法分析

时间复杂度