專欄：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算法文檔 。