Java經典演算法：具有上限的子陣列數

給定一個由正整陣列成的陣列A，以及兩個正整數L和R（L <= R）。

返回（連續的非空）子陣列的數量，以使該子陣列中最大陣列元素的值至少為L，至多為R。

示例：

輸入：

A = ［2，1，4，3］

L = 2

R = 3

輸出：3

說明：有三個滿足要求的子陣列：［2］，［2、1］，［3］。

Java解決方案

此問題的邊界是每個元素的總和，而不是總和。很容易誤解這個問題，因為有很多與總和有關的問題。

給定樣本［2，1，4，3］中的陣列，我們可以將其轉換為陣列［0，0，1，0］，這意味著如果元素在邊界內，則為0。子陣列的數量。

給定一個數組，子陣列的總數遵循以下模式：

［0］-> 1

［0，0］-> 2 + 1（單元素子陣列+ 2元素子陣列）

［0，0，0］-> 3 + 2 + 1

［0，0，0，0］-> 4 + 3 + 2 + 1

因此，解決方案是R的countBelowBoundary-（L-1）的countBelowBoundary。

public

int

numSubarrayBoundedMax（

int

［］ A，

int

L，

int

R） {

return

countBelowBoundary（A， R）-countBelowBoundary（A，L-1）；}

public

int

countBelowBoundary（

int

［］ A，

int

bound）{

int

count = 0；

int

temp = 0；

for

（

int

a： A）{

if

（a<=bound）{

temp = temp +1；

count += temp；

}

else

{

temp = 0；

}

}

return

count；}

時間為O（N），空間為O（1）。

最後，開發這麼多年我也總結了一套學習Java的資料與面試題，如果你在技術上面想提升自己的話，可以關注我，私信傳送領取資料或者在評論區留下自己的聯絡方式，有時間記得幫我點下轉發讓跟多的人看到哦。