209. 長度最小の部分配列#
正の整数 n 個を含む配列と正の整数 target が与えられます。
配列の中で、合計が target 以上となる最小の連続する部分配列 の長さを求め、その長さを返します。条件を満たす部分配列が存在しない場合は、0 を返します。
例 1：
入力：target = 7, nums = [2,3,1,2,4,3]
出力：2
説明：条件を満たす最小の部分配列は [4,3] です。
例 2：
入力：target = 4, nums = [1,4,4]
出力：1
例 3：
入力：target = 11, nums = [1,1,1,1,1,1,1,1]
出力：0
ヒント：
進んだ内容：
- もし既に
O(n)の時間計算量の解法を実装している場合、O(n log(n))の時間計算量の解法を試してみてください。
2 つのポインタ#
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int i = 0, j = 0;
int cur = 0;
int res = INT_MAX;
while (j < n) {
cur += nums[j];
while (cur >= target) {
res = min(res, j - i + 1);
cur -= nums[i];
++i;
}
++j;
}
return res == INT_MAX ? 0 : res;
}
};
プレフィックス和#
区間の和はプレフィックス和と関連しています。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
vector<int> prev(n + 1, 0);
// prev[i] は nums のインデックス [0, i) の区間和を表します
for (int i = 1; i <= n; ++i) {
prev[i] = prev[i - 1] + nums[i - 1];
}
int res = INT_MAX;
for (int i = 0; i < n; ++i) {
// prev[j] - prev[i] は nums のインデックス [i, j) の区間和を表します
// prev[j] - prev[i] >= target を満たす必要があります
// よって、prev[j] >= target + prev[i] となります
int find_val = target + prev[i];
// prev は非減少の列なので、二分探索を使って区間の右側のインデックスを見つけます
auto iter = lower_bound(prev.begin(), prev.end(), find_val);
if (iter != prev.end()) {
res = min(res, static_cast<int>(iter - prev.begin()) - i);
// iter は実際に必要なインデックスよりも 1 多い位置にあるため、1 を加える必要はありません
}
}
return res == INT_MAX ? 0 : res;
}
};