本文主要是介绍Lintcode 994 · Contiguous Array (presum + hashmap好题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
994 · Contiguous Array
Algorithms
The length of the given binary array will not exceed 50,000.
Example
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
这题应该是不能用滑动窗口做的。我试了很久，发现不行。不知道有没有高人能用滑动窗口做出来。
解法1：用presum + hashmap
class Solution {
public:/*** @param nums: a binary array* @return: the maximum length of a contiguous subarray*/int findMaxLength(vector<int> &nums) {int n = nums.size();if (n == 0) return 0;unordered_map<int, int> um; //<presum, pos>vector<int> presums(n + 1, 0);int res = 0;um[0] = 0;for (int i = 1; i <= n; i++) {presums[i] = presums[i - 1] + (nums[i - 1] == 0 ? -1 : 1);if (um.find(presums[i]) == um.end()) {um[presums[i]] = i;} else {res = max(res, i - um[presums[i]]);}}return res;}
};
这篇关于Lintcode 994 · Contiguous Array (presum + hashmap好题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
