【剑指offer专项】11. 0 和 1 个数相同的子数组

思路:

  1. 将数组中0元素转为-1,则数组元素和=0代表0与1元素个数相等。此时就可以利用前缀和=0来判断子数组中0与1元素相同。

  2. 因为要找最长的子数组,所以哈希表中只存前缀和第一次出现的下标。(如果是找所以0和1的子数组就不能这样)

对应代码和注释如下:

class Solution {
public:
	int findMaxLength(vector<int>& nums) {
		int counter = 0;
		unordered_map<int, int>map;
		map[counter] = -1;
		int maxres = 0;
		for (int i = 0; i < nums.size(); i++){//遍历每个下标的前缀和,并存储到容器中
			int newnum = nums[i];
			if (newnum==1)counter += 1;
			else counter += -1;
			if (map.count(counter)){//哈希表中找counter
			int length = i - map[counter];
				maxres = max(maxres, length);
			}
			else{//在哈希表中记录counter第一次出现的下标
				map[counter] = i;
			}
		}
		return maxres;
	}
};

版权声明:本文为qq_42800363原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。