专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

一前阿里巴巴的员工最近发文称：自己35岁，年薪百万，还是技术专家，被一个空降的95后嫡系领导逼到离职。说他代码水平不如应届生，不想干可以走。

都技术专家了，代码水平肯定不会差的，即便代码水平差，也应该是由经验更足的人来评价。假如一个 5 年工作经验的对一个 1 年工作经验的说你的代码水平差，能理解。但一个 1 年工作经验的对一个 5 工作经验的说你的代码水平很差，就感觉有点找茬了，但也不排除个别 5 年工作经验的确实比较水。

但发文的作者都已经是技术专家了，水平不会差的，所以空降的95后领导很可能是来搞事的。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第1477题：找两个和为目标值且不重叠的子数组，难度是中等。

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

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

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

示例1：

输入：arr = [7,3,4,7], target = 7 输出：2 解释：尽管我们有 3 个互不重叠的子数组和为 7 （[7], [3,4] 和 [7]），但我们会选择第一个和第三个子数组，因为它们的长度和 2 是最小值。

示例2：

输入：arr = [4,3,2,6,2,3,4], target = 6 输出：-1 解释：我们只有一个和为 6 的子数组。

  • 1 <= arr.length <= 10^5

  • 1 <= arr[i] <= 1000

  • 1 <= target <= 10^8

问题分析

这题说的是找出两个子数组，他们的和都等于target，并且这两个子数组还不能重叠，如果有多个这样的子数组，返回长度和的最小值。

如果只是计算子数组之和等于target，我们可以使用滑动窗口，但这题即要保证两个子数组之和等于target，又要保证这两个子数组不能重叠。这里我们可以使用滑动窗口加动态规划来解决。

我们定义dp[i]表示子数组[0,i-1]中满足和为target的最小子数组长度，如果某个子数组[m,n]的和为target，我们只需要在子数组[0,m-1]中找个一个满足条件的最小长度即可，这个最小长度就是dp[m]，最后还需要保存最小长度。

JAVA：

public int minSumOfLengths(int[] arr, int target) {     int left = 0, right = 0, n = arr.length;     // dp[i+1]表示子数组[0,i]中满足和为target的数组最小长度。     int[] dp = new int[n + 1];     dp[0] = n;     int ans = Integer.MAX_VALUE;     int sum = 0;// 窗口中元素的和。     while (right < n) {         sum += arr[right];         while (sum > target)// 窗口中的元素之和不能大于target。             sum -= arr[left++];         if (sum == target) {// 窗口中的元素之和等于target。             int len = right - left + 1;// 窗口长度             ans = Math.min(ans, dp[left] + len);             dp[right + 1] = Math.min(dp[right], len);         } else {// 窗口中的元素之后小于target。             dp[right + 1] = dp[right];         }         right++;// 滑动窗口右边界。     }     return ans > n ? -1 : ans; }

C++：

public:     int minSumOfLengths(vector

 &arr, int target) {         int left = 0, right = 0, n = arr.size();         // dp[i+1]表示子数组[0,i]中满足和为target的数组最小长度。         vector

  dp(n + 1, 0);         dp[0] = n;         int ans = INT_MAX;         int sum = 0;// 窗口中元素的和。         while (right < n) {             sum += arr[right];             while (sum > target)// 窗口中的元素之和不能大于target。                 sum -= arr[left++];             if (sum == target) {// 窗口中的元素之和等于target。                 int len = right - left + 1;// 窗口长度                 ans = min(ans, dp[left] + len);                 dp[right + 1] = min(dp[right], len);             } else {// 窗口中的元素之后小于target。                 dp[right + 1] = dp[right];             }             right++;// 滑动窗口右边界。         }         return ans > n ? -1 : ans;     }

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。