LeetCode第201回週試合1546.Maximum Number of Non-Overlapping Subarrays With Sum Equals Target
Leetcode 1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target タイトル説明 構想 週間試合コード 最適化コード 複雑度分析 タイトルの説明
Given an array nums and an integer target.
Return the maximum number of non-empty non-overlapping subarrays such that the sum of values in each subarray is equal to target.
Example 1:
Input: nums = [1,1,1,1,1], target = 2 Output: 2 Explanation: There are 2 non-overlapping subarrays [1,1,1,1,1] with sum equals to target(2). Example 2:
Input: nums = [-1,3,5,1,4,2,-9], target = 6 Output: 2 Explanation: There are 3 subarrays with sum equal to 6. ([5,1], [4,2], [3,5,1,4,2,-9]) but only the first 2 are non-overlapping. Example 3:
Input: nums = [-2,6,6,3,5,4,1,2,8], target = 10 Output: 3 Example 4:
Input: nums = [0,0,0], target = 0 Output: 3
Constraints:
1 <= nums.length <= 105 -104<= nums[i] <= 104 0 <= target <= 106
テーマは1つの配列を与えて、重ならない和を求めてtargetのサブ配列のために最大で同時にどれだけ存在します.データ規模から見ると,配列は最長10万であり,アルゴリズムの複雑さはo(nlogn)以下であるに違いない.n 2はきっと通れないに違いない.
構想
一般的にサブ配列和を解く問題はまず順方向積算和(presum)を考慮する.現在のpressumがsである場合、pressumがs-t(tはtargetを表し、簡単に書く)であるかどうかを探すだけで、現在の数字で終わり、tを満たすネタ配列が存在します.これまでpresumはs-tで出現した位置が複数ある可能性がありますが、どれを取りますか?答えは最後に現れたものを取ります.長さが長ければ長いほど、最後の結果はチャンスが大きくなるという結論が分かりやすい.前のm個の数字で最大k個の条件を満たす重複しない配列を見つけることができる.その前のm+1個の数字は前のm個の数字より結果が悪いに違いない.少なくとも前のm個の数を満たすその最適解は前のm+1個の数字の中でまだ実行可能な解である.したがって、resの値は、長さが増加するにつれて単調に減少しない可能性があります.
当时、周の试合をする时私はhash mapでdpを配合してdp[i]を解いて前のiの個数が求めることができる最良の解を表すことを思い付いて、前の说明によって、dp[i]の値はきっと単调で减らないindex[presum]で前のpresumが现れた位置を表します
週間試合コード
このコードの構想は,s−tが前回出現した位置を先に見つけ,その位置の最適解を用いて現在の可能な最適解を計算することである.
最適化コード
discussの中の高票の答えを見て、自分の周試合のコードの中にいくつかの冗長さがあることを発見して、周試合のコードの中でpresumを通じてindexを見つけて、それからindexによって前の最適解を探します.実はこの必要はありません.indexというステップは完全に省くことができます.現在の累積とバンドルの最適解がどれだけあるかを記録するだけでいいです.たとえ前に現在のpresumが現れたとしても、現在のものは前のものより悪くないに違いない(単調性の結論)、ましてs-tを探すたびに、最後に現れたものを探すのは、最後に現れたものがカバーする範囲が最も大きいからだ.
複雑度分析
時間空間はすべてo(n)
この問題は本質的に2 sumとあまり差がなく,res単調性を利用して貪欲さを用いることができる.
Given an array nums and an integer target.
Return the maximum number of non-empty non-overlapping subarrays such that the sum of values in each subarray is equal to target.
Example 1:
Input: nums = [1,1,1,1,1], target = 2 Output: 2 Explanation: There are 2 non-overlapping subarrays [1,1,1,1,1] with sum equals to target(2). Example 2:
Input: nums = [-1,3,5,1,4,2,-9], target = 6 Output: 2 Explanation: There are 3 subarrays with sum equal to 6. ([5,1], [4,2], [3,5,1,4,2,-9]) but only the first 2 are non-overlapping. Example 3:
Input: nums = [-2,6,6,3,5,4,1,2,8], target = 10 Output: 3 Example 4:
Input: nums = [0,0,0], target = 0 Output: 3
Constraints:
1 <= nums.length <= 105 -104<= nums[i] <= 104 0 <= target <= 106
テーマは1つの配列を与えて、重ならない和を求めてtargetのサブ配列のために最大で同時にどれだけ存在します.データ規模から見ると,配列は最長10万であり,アルゴリズムの複雑さはo(nlogn)以下であるに違いない.n 2はきっと通れないに違いない.
構想
一般的にサブ配列和を解く問題はまず順方向積算和(presum)を考慮する.現在のpressumがsである場合、pressumがs-t(tはtargetを表し、簡単に書く)であるかどうかを探すだけで、現在の数字で終わり、tを満たすネタ配列が存在します.これまでpresumはs-tで出現した位置が複数ある可能性がありますが、どれを取りますか?答えは最後に現れたものを取ります.長さが長ければ長いほど、最後の結果はチャンスが大きくなるという結論が分かりやすい.前のm個の数字で最大k個の条件を満たす重複しない配列を見つけることができる.その前のm+1個の数字は前のm個の数字より結果が悪いに違いない.少なくとも前のm個の数を満たすその最適解は前のm+1個の数字の中でまだ実行可能な解である.したがって、resの値は、長さが増加するにつれて単調に減少しない可能性があります.
当时、周の试合をする时私はhash mapでdpを配合してdp[i]を解いて前のiの個数が求めることができる最良の解を表すことを思い付いて、前の说明によって、dp[i]の値はきっと単调で减らないindex[presum]で前のpresumが现れた位置を表します
週間試合コード
const int N = 1e5 + 10;
//dp[i] i
int dp[N];
class Solution {
public:
int maxNonOverlapping(vector<int>& nums, int t) {
memset(dp, 0, sizeof dp);
unordered_map<int, int> index; //key index, value [0,key]
int n = nums.size();
index[0] = -1;
int s = 0; // presum
int res = 0;
for ( int i = 0; i < n; ++i ) {
s += nums[i];
if ( index.count(s - t) ) {
// index[s-t]+1 dp[i] i ， index 1
res = max(res, dp[index[s - t] + 1] + 1);
}
index[s] = i;
dp[i + 1] = res;
}
return res;
}
};
このコードの構想は,s−tが前回出現した位置を先に見つけ,その位置の最適解を用いて現在の可能な最適解を計算することである.
最適化コード
discussの中の高票の答えを見て、自分の周試合のコードの中にいくつかの冗長さがあることを発見して、周試合のコードの中でpresumを通じてindexを見つけて、それからindexによって前の最適解を探します.実はこの必要はありません.indexというステップは完全に省くことができます.現在の累積とバンドルの最適解がどれだけあるかを記録するだけでいいです.たとえ前に現在のpresumが現れたとしても、現在のものは前のものより悪くないに違いない(単調性の結論)、ましてs-tを探すたびに、最後に現れたものを探すのは、最後に現れたものがカバーする範囲が最も大きいからだ.
class Solution {
public:
int maxNonOverlapping(vector<int>& nums, int t) {
unordered_map<int, int> sum; //key presum， value presum
int n = nums.size();
sum[0] = 0;
int presum = 0;
int res = 0;
for ( int i = 0; i < n; ++i ) {
presum += nums[i];
if ( sum.count(presum - t) ) {
res = max(res, sum[presum - t] + 1);
}
sum[presum] = res;
}
return res;
}
};
複雑度分析
時間空間はすべてo(n)
この問題は本質的に2 sumとあまり差がなく,res単調性を利用して貪欲さを用いることができる.