文章目錄

• • • 本題分析
    • 題目鏈接

本題分析

題目重述： 給定一個非負的數(shù)組，要求將其分成3個非空的三段，要求每一段的數(shù)字之和依次遞增（可以相等），求總共有幾種分法。

題目解答：

雙指針算法

思路：枚舉第二個分界點，看第一個分界點有多少種選擇 。

數(shù)組下標從1開始，即從1到n: a[1] ,a[2],…a[n]， 第二個分界點下標是i，第一個分界點下標是x，這里下標屬于后一段。這樣把數(shù)組分成三段(用下標來表示)：[1~x-1], [x ~i-1],[ i ~ n]. 三段之和分別記為A，B，C。

對于分界點i，我們看第一個分界點x的取值范圍，假設(shè)其可取的最小下標為j，可取的最大下標為k，那么對于第二個分界點i，滿足題意的方案數(shù)就有：k-j+1 種。

比如樣例，

輸入：nums = [1,2,2,2,5,0] 輸出：3 解釋：nums 總共有 3 種好的分割方案： [1] [2] [2,2,5,0] [1] [2,2] [2,5,0] [1,2] [2,2] [5,0] 下標從1開始123456

數(shù)組內(nèi)容	1	2	2	2	5	0

假設(shè)第二個分界點下標i=4，則C=7，第一個分界點x可取多少呢？ (j,k)=(3,3)，故此時的方案數(shù)： 3-3+1=1種。

假設(shè)第二個分界點 i=5，則C=5，那么第一個分界點x可取多少呢？ (j,k)=(3,4)，故此時的方案數(shù)： 4-3+1=2種。

總的方案數(shù)就是1+2=3種。

下面的問題就是這個 j和k 怎么求？

j的含義是：i給定之后， 第一個分界點最靠前可以取到什么位置。

i需要滿足什么呢？

j越往左走，那么中間B就會越大，為了滿足B≤C，那么必然j有下界。

在第二個分界點往后走的時候，C在變小，為了滿足B≤C，j也應(yīng)該往后走。也就是說，j會隨著i向右移而單調(diào)向右移。

k的含義是：i給定之后，第二個分界點最靠后可以取到什么位置。

k需要滿足什么呢？

k需要滿足a[k]~a[i-1]的和≥ a[1] ~a[k-1]的和，即B≥A。

k往右走，在i固定時，B會變小，A會變大，為了滿足B≥A，必然存在一個最大的k，越過了這個邊界，就不再滿足B≥A。

根據(jù)上面 j的推理，可以利用反證法證明， k會隨著i向右移而單調(diào)向右移。

總之：最小取值j由右邊(C≥B)限制， 最大取值 k由左邊（A≤B）限制。

當(dāng)然還有小技巧：可以使用前綴和來求出一段的和：通過O(1)的時間求出一段的和。

注意：下面對代碼進行解釋

對于邊界(j,k)的判斷思路不太一樣

while(s[n]-s[i-1] < s[i-1]-s[j-1]) j++; while( k+1<i && s[k] <= s[i-1]-s[k]) k++;

下面進行解釋：

對于 左邊界j：左邊界被右邊限制，只要B大于C，j就一直j++，直到第一個滿足B小于等于C。這就是滿足題意的第一個分界點的最小取值，即左邊界。

對于右邊界k：右邊界k被左邊限制，我們要試探性地往右走：對于下標是k+1的第一個分界點，是否滿足 A小于等于B，如果滿足，就繼續(xù)k++。當(dāng)然，第一個下標永遠小于第二個下標i，嘗試k+1時也要滿足k+1<i.

ac代碼

class Solution { public:int waysToSplit(vector<int>& nums) {int n = nums.size(),mod = 1e9 +7;vector<int> s(n+1); //前綴和數(shù)組for(int i=1;i<=n;i++) s[i] =s[i-1]+nums[i-1]; //下標往后移動了一個，從1開始int res=0;//枚舉第二個分界點i,記住下標從1開始for( int i=3, j=2, k=2; i<= n; i++){//判斷(j,k)的位置//對于左邊界j：如果B＞C，j一直往右移動，直到B≤Cwhile(s[n]-s[i-1] < s[i-1]-s[j-1]) j++;//對于右邊界k： 如果A一直小于等于B,k就一直往右移//本身是A小于等于B 即[1,k-1] ≤ [k,i-1]//試探一下，看k取k+1是否成立，如果成立就k++。//現(xiàn)在要試探k+1 即 [1,k] ≤ [k+1, i-1]while( k+1<i && s[k] <= s[i-1]-s[k]) k++;if(j<=k && s[k-1] <= s[i-1]-s[k-1] && s[n]-s[i-1] >= s[i-1]-s[j-1] )res=( res+ k-j+1) %mod;}return res;} };

題目鏈接

Leetcode1712. 將數(shù)組分成三個子數(shù)組的方案數(shù)

總結(jié)

以上是生活随笔為你收集整理的Leetcode1712. 将数组分成三个子数组的方案数[C++题解]：双指针和前缀和的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。