O(n) time O(n) space
把0改成-1，题目变成找最长的和为0的连续子数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int findMaxLength(vector<int>& nums) {
unordered_map<int, int> m;
int n = nums.size(), res = 0, diff = 0;
m[0] = -1;
for (int i = 0; i < n; ++i) {
diff += (nums[i] == 1 ? 1 : -1);
if (m.count(diff)) {
res = max(res, i - m[diff]);
} else {
m[diff] = i;
}
}
return res;
}
};
|