题目描述

给你一个整数数组arr和一个整数值target。

请你在arr中找两个互不重叠的子数组且它们的和都等于target。可能会有多种方案，请你返回满足要求的两个子数组长度和的最小值。

请返回满足要求的最小长度和，如多无法找到这样的两个子数组，请返回**-1**。

思路与算法

如果存在多个以i下标结尾的子数组满足要求，则选择其中长度最短的那一个。因为如果一个较长的子数组可以作为答案中的一部分，换成一个较短的子数组，也同样成立，同时满足总和更短。（贪心的思想）

1. 首先，使用一个map来记录<前缀和，结尾下标>的映射信息。一个vector记录当前下标之前满足要求的最短子数组长度。

2. 利用当前前缀和 - target判断是否存在目标子数组区间。若存在，则得出对应子数组长度，并与当前位置之前的最短子数组长度比较，将较小值存入一个vector中；否则，则存入0。

3. 得到一个满足要求的最短子数组后，以该子数组的起始下标为结尾，搜索vector中是否存在满足要求的第二个子数组，若存在，则记录两子数组长度和，并与当前最短的两个子数组之和进行比较，取小。

4. 经过一轮遍历之后，输出结果。

   代码

   class Solution {
   public:
       int minSumOfLengths(vector<int>& arr, int target) {
          unordered_map<int, int> M;	// 用于<前缀和，结尾下标>的映射
          int t = 0;
          int ans = 2e9;
          vector<int> len;		// 记录到每个位置，和为target的最短子数组的长度
          int mi = 0;			// 当前满足和为target的最短子数组的长度
          M[0] = -1;
          for(int i = 0; i < arr.size(); i++){
              t += arr[i];
              M[t] = i;
              if(M.count(t - target)){
                  int l = M[t-target];
                  int x = i - l;
                  if(mi == 0)  mi = x;
                  else mi = min(mi, x);
                  len.push_back(mi);
                  if(l != -1 && len[l] != 0){	// 不是第一个满足条件的子数组
   				   ans = min(ans, len[l] + x);
                  }
              }else{
                  len.push_back(mi);
              }
          }
          if(ans == 2e9)   return -1;
          return ans;
       }
   
   };

   复杂度分析

   • 时间复杂度：一轮循环遍历，时间复杂度为O(n)。

   • 空间复杂度：用于哈希映射的map，以及记录目标子数组长度的vector，故空间复杂度为O(n)。