image.png

思路：滑动窗口 + 哈希表

  • 此题等于在问：不重复子数组的最大和是多少
  • 哈希表不一定快，自己可以写一个record数组
  • 两个指针，同时从0出发，如果发现右边指针指向的数字已经在rec中了，那么就不断移动左边的指针，直到右边的数字不在rec中。然后，插入右边的数字，不断更新，得到需要的数值。
  1. class Solution {
  2. public:
  3.     int maximumUniqueSubarray(vector<int>& nums) {
  4.         int max_val = 0, cur_val = 0;
  5.         int len_nums = nums.size();
  6.         unordered_set<int> rec_nums;
  7.         for (int left = 0, right = 0; right < len_nums; ) {
  8.             while(rec_nums.count(nums[right])) {
  9.                 cur_val -= nums[left];
  10.                 rec_nums.erase(nums[left++]);
  11.             }
  12.             rec_nums.insert(nums[right]);
  13.             cur_val += nums[right];
  14.             max_val = max(max_val, cur_val);
  15.             ++right;
  16.         }
  18.         return max_val;
  19.     }
  20. };