Contiguous Array
2020/5/26, 2020/4/13
問題概要
[1, 0, 0, 1, 0, 1, 1]みたいな0, 1どちらかがランダムに入った数列が渡される
0, 1の両方が同数含まれるsubarrayの最長の長さを求めよ、という問題
解法
色んな解法を調べてると、mapを使えばO(N)で解けることが分かった
-1, 1の数列に変換して、水位の浮き沈みみたいに再度その水の高さが戻ればその区間を保存する、というやり方だと確かにスマート
code:solution.cpp
class Solution {
public:
int findMaxLength(vector<int>& nums) {
int ans = 0;
int cur_sum = 0;
// 任意のindexまでの0, 1の出現数がイコールになる"直前"のindexを格納するためのmap
unordered_map<int, int> m{{0, -1}};
for (int i=0; i<nums.size(); i++) {
cur_sum += (numsi == 1) ? 1 : -1; // 一度mにkeyとしてcur_sumが格納されてるなら、
// mcur_sumからidxまでの区間は1, 0の出現数が等しいことになるので // m.count(cur_sum)はtrueになる
if (m.count(cur_sum)) ans = max(ans, i-mcur_sum); // 初めて出会う水位(cur_sum)であればmに格納
}
return ans;
}
};
/icons/-.icon
TLEになったコード
code:TLE_solution.cpp
class Solution {
public:
int findMaxLength(vector<int>& nums) {
if (nums.size() < 2) return 0;
// first is zero, second is one
vector<pair<int, int>> dp = {make_pair(0, 0)};
for (int i=0; i<nums.size(); i++) {
pair<int, int> prev = dp.back();
if (numsi == 0) dp.push_back(make_pair(prev.first+1, prev.second)); else dp.push_back(make_pair(prev.first, prev.second+1));
}
// ここまでで正しいdpを作れてるが、以降の処理が枝切りしてるものの計算量がO(N^2)でTLEになってしまう
// make_pairはコストが高いのかもしれない
pair<int, int> tmp = make_pair(0, 0);
for (int i=dp.size()-1; i>0; i--) {
for (int j=0; j<i; j++) {
int zeros = dpi.first - dpj.first; int ones = dpi.second - dpj.second; if (zeros == ones && tmp.first < zeros) {
tmp = make_pair(zeros, ones);
continue;
}
}
}
return tmp.first * 2;
}
};