日期：2026年9月17日
LeetCode 題目連結：1477. Find Two Non-overlapping Sub-arrays Each With Target Sum
解題想法
中等難度題，題目給一個陣列 $arr$ 與一個整數 $target$，要找出 $2$ 個不重疊、加總等於 $target$ 的連續子陣列，回傳這兩個子陣列長度相加的最小值。題目下方有提示：
- 建立一個陣列 $prefix$，$prefix[i]$ 代表在 $i$ 之前結束、加總等於 $target$ 的連續子陣列最短長度。再建立一個陣列 $suffix$，$suffix[i]$ 代表從 $i$ 開始、加總等於 $target$ 的連續子陣列最短長度。
- 檢查 $i = 0$ 到 $i = n-1$，找出 $prefix[i] + suffix[i]$ 的最小值。
- 如果在建立 $prefix, suffix$ 時遇到困難，可以先將所有的值都設定成無窮大，分別先找出加總等於 $target$ 的前綴、後綴連續子陣列長度，之後再轉換成最短長度。
Python 程式碼
Runtime: 260 ms, beats 29.61%. Memory: 31.07 MB, beats 83.24%.
class Solution:
def minSumOfLengths(self, arr: List[int], target: int) -> int:
n = len(arr) # 長度
maxn = n + 1 # 長度加 1，答案不可能大於 n
# 1. 用滑動視窗找 prefix
prefix = [maxn] * n # prefix[i] 代表於 i-1 結束，子陣列和等於 target 的長度
rsum, left = 0, 0
for right in range(n - 1):
rsum += arr[right]
while left < right and rsum > target:
rsum -= arr[left]
left += 1
if rsum == target:
length = right - left + 1
prefix[right + 1] = min(prefix[right + 1], length)
# 2. 再將 prefix[i] 改成從左往右找，於 i-1 結束、子陣列和等於 target 的最短長度
pmin = maxn
for i in range(1, n):
if prefix[i] < pmin:
pmin = prefix[i]
elif prefix[i] > pmin:
prefix[i] = pmin
# 3. 用滑動視窗找 prefix
suffix = [maxn] * n # suffix[i] 代表於 i 結束，後綴子陣列和等於 target 的長度
lsum, ri = 0, n-1
for le in range(n-1, -1, -1):
lsum += arr[le]
while ri > le and lsum > target:
lsum -= arr[ri]
ri -= 1
if lsum == target:
length = ri - le + 1
suffix[le] = min(suffix[le], length)
# 4. 再將 suffix[i] 改成從右往左找，於 i 結束、後綴子陣列和等於 target 的最短長度
smin = maxn
for i in range(n-1, -1, -1):
if suffix[i] < smin:
smin = suffix[i]
elif suffix[i] > smin:
suffix[i] = smin
# 5. 答案預設為 maxn * 2，從 i = 0 ~ n-1 找 prefix[i] + suffix[i] 的最小值
ans = maxn * 2
for i in range(n):
if prefix[i] < maxn and suffix[i] < maxn:
ans = min(ans, prefix[i] + suffix[i])
# 如果 ans 小於預設值，回傳 ans；反之回傳 -1
return ans if ans < maxn * 2 else -1
Runtime: 207 ms, beats 36.31%. Memory: 31.22 MB, beats 57.54%.
class Solution:
def minSumOfLengths(self, arr: List[int], target: int) -> int:
n = len(arr) # 長度
maxn = n + 1 # 長度加 1，答案不可能大於 n
# 1. 用滑動視窗找 prefix
prefix = [maxn] * n # prefix[i] 代表於 i-1 結束，子陣列和等於 target 的最短長度
pmin, rsum, left = maxn, 0, 0
for right in range(n - 1):
rsum += arr[right]
while left < right and rsum > target:
rsum -= arr[left]
left += 1
if rsum == target:
pmin = min(pmin, right - left + 1)
prefix[right + 1] = pmin
# 2. 用滑動視窗找 prefix
suffix = [maxn] * n # suffix[i] 代表於 i 結束，後綴子陣列和等於 target 的最短長度
smin, lsum, ri = maxn, 0, n-1
for le in range(n-1, -1, -1):
lsum += arr[le]
while ri > le and lsum > target:
lsum -= arr[ri]
ri -= 1
if lsum == target:
smin = min(smin, ri - le + 1)
suffix[le] = smin
# 3. 答案預設為 maxn * 2，從 i = 0 ~ n-1 找 prefix[i] + suffix[i] 的最小值
ans = maxn * 2
for i in range(n):
if prefix[i] < maxn and suffix[i] < maxn:
ans = min(ans, prefix[i] + suffix[i])
# 如果 ans 小於預設值，回傳 ans；反之回傳 -1
return ans if ans < maxn * 2 else -1
C++ 程式碼
Runtime: 18 ms, beats 50.26%. Memory: 92.38 MB, beats 47.68%.
class Solution {
public:
int minSumOfLengths(vector<int>& arr, int target) {
int n = (int)arr.size(); // 長度
int maxn = n + 1; // 長度加 1，答案不可能大於 n
/* 1. 用滑動視窗找 prefix */
vector<int> prefix (n, maxn); // prefix[i] 代表於 i-1 結束，子陣列和等於 target 的長度
int rsum = 0, left = 0;
for(int right = 0; right < n-1; right++) {
rsum += arr[right];
while(left < right && rsum > target) {
rsum -= arr[left];
left++;
}
if (rsum == target) {
int length = right - left + 1;
prefix[right + 1] = min(prefix[right + 1], length);
}
}
/* 2. 再將 prefix[i] 改成從左往右找，於 i-1 結束、子陣列和等於 target 的最短長度 */
int pmin = maxn;
for(int i = 1; i < n; i++) {
if (prefix[i] < pmin) {
pmin = prefix[i];
} else if (prefix[i] > pmin) {
prefix[i] = pmin;
}
}
/* 3. 用滑動視窗找 prefix */
vector<int> suffix (n, maxn); // suffix[i] 代表於 i 結束，後綴子陣列和等於 target 的長度
int lsum = 0, ri = n-1;
for(int le = n-1; le >= 0; le--) {
lsum += arr[le];
while(ri > le && lsum > target) {
lsum -= arr[ri];
ri--;
}
if (lsum == target) {
int length = ri - le + 1;
suffix[le] = min(suffix[le], length);
}
}
/* 4. 再將 suffix[i] 改成從右往左找，於 i 結束、後綴子陣列和等於 target 的最短長度 */
int smin = maxn;
for(int i = n-1; i >= 0; i--) {
if (suffix[i] < smin) {
smin = suffix[i];
} else if (suffix[i] > smin) {
suffix[i] = smin;
}
}
/* 5. 答案預設為 maxn * 2，從 i = 0 ~ n-1 找 prefix[i] + suffix[i] 的最小值 */
int ans = maxn * 2;
for(int i = 0; i < n; i++) {
if (prefix[i] < maxn && suffix[i] < maxn) {
ans = min(ans, prefix[i] + suffix[i]);
}
}
// 如果 ans 小於預設值，回傳 ans；反之回傳 -1
return (ans < maxn * 2 ? ans : -1);
}
};
Runtime: 13 ms, beats 55.15%. Memory: 92.37 MB, beats 47.68%.
class Solution {
public:
int minSumOfLengths(vector<int>& arr, int target) {
int n = (int)arr.size(); // 長度
int maxn = n + 1; // 長度加 1，答案不可能大於 n
/* 1. 用滑動視窗找 prefix */
vector<int> prefix (n, maxn); // prefix[i] 代表於 i-1 結束，子陣列和等於 target 的最短長度
int pmin = maxn, rsum = 0, left = 0;
for(int right = 0; right < n-1; right++) {
rsum += arr[right];
while(left < right && rsum > target) {
rsum -= arr[left];
left++;
}
if (rsum == target) {
int length = right - left + 1;
if (length < pmin) {
pmin = length;
}
}
prefix[right + 1] = pmin;
}
/* 2. 用滑動視窗找 prefix */
vector<int> suffix (n, maxn); // suffix[i] 代表於 i 結束，後綴子陣列和等於 target 的最短長度
int smin = maxn, lsum = 0, ri = n-1;
for(int le = n-1; le >= 0; le--) {
lsum += arr[le];
while(ri > le && lsum > target) {
lsum -= arr[ri];
ri--;
}
if (lsum == target) {
int length = ri - le + 1;
if (length < smin) {
smin = length;
}
}
suffix[le] = smin;
}
/* 3. 答案預設為 maxn * 2，從 i = 0 ~ n-1 找 prefix[i] + suffix[i] 的最小值 */
int ans = maxn * 2;
for(int i = 0; i < n; i++) {
if (prefix[i] < maxn && suffix[i] < maxn) {
if (prefix[i] + suffix[i] < ans) {
ans = prefix[i] + suffix[i];
}
}
}
// 如果 ans 小於預設值，回傳 ans；反之回傳 -1
return (ans < maxn * 2 ? ans : -1);
}
};
沒有留言:
張貼留言