Problem
题目大意：求最长子数组，要求其中0和1的数量相等。
Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.
Example 1:
Input: [0,1] Output: 2 Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.
Example 2:
Input: [0,1,0] Output: 2 Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.
Note: The length of the given binary array will not exceed 50,000.
Solution: HashTable
Prefix sum + hashtable
Time complexity: O(n)
Space complexity: O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua // Running time: 143 ms class Solution { public: int findMaxLength(vector<int>& nums) { if (nums.empty()) return 0; unordered_map<int, int> pos; int sum = 0; int ans = 0; for (int i = 0; i < nums.size(); ++i) { sum += nums[i] ? 1 : -1; if (sum == 0) { ans = i + 1; } else if (pos.count(sum)) { ans = max(ans, i - pos[sum]); } else { pos[sum] = i; } } return ans; } }; |
V2: Using array instead of a hashtable
Time complexity: O(2*n + 1 + n)
Space complexity: O(2*n + 1)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua // Running time: 102 ms (<96.8 %) class Solution { public: int findMaxLength(vector<int>& nums) { if (nums.empty()) return 0; const int n = nums.size(); vector<int> pos(2 * n + 1, INT_MIN); int sum = 0; int ans = 0; for (int i = 0; i < nums.size(); ++i) { sum += nums[i] ? 1 : -1; if (sum == 0) { ans = i + 1; } else if (pos[sum + n] != INT_MIN) { ans = max(ans, i - pos[sum + n]); } else { pos[sum + n] = i; } } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment