只有0_1的数组

对上一篇博客问题进行改进https://blog.csdn.net/qq_41864967/article/details/85084614

给定一个只包含0或1的数组，找出其中包含相同0的个数和1的个数的最
长子序列，输出子序列的长度, 要求在O(n)的时间复杂度内完成。
如：对于数组[0,0,1,1,0]，输出结果为4。子序列[0,0,1,1] 或
[0,1,1,0] 为符合条件的最长子序列，包含了两个1和两个0，个数相同。

******************************************************************************************

思路：

将所有0变为-1   0和1数目相等 就变成了求子数组和为0的最大长度

    public static int maxLengthIn01(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] == 0) {
				arr[i] = -1;
			}
		}
		int res = maxLength(arr, 0);
		return res;

	}

	public static int maxLength(int[] arr, int aim) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		// key 某个累加和sum value 这个累加和最早出现的次数
		// 取以每个位置为结尾的等于定值的子数组的最大长度的最大值
		HashMap<Integer, Integer> map = new HashMap<>();
		map.put(0, -1); // 非常重要 意思是累加和为0 最早出现的位置为 -1 默认
		int res = 0;
		int sum = 0; // 前缀和 到i位置
		for (int i = 0; i < arr.length; i++) {
			sum += arr[i]; // arr[0..i]的和 到当前位置的累加和
			if (map.containsKey(sum - aim)) { // 能找到sum-aim出现的最早位置
				// i-map.get(sum-aim)：用当前位置（和为sum）-sum-aim出现的最早位置 则剩下的和为aim
				res = Math.max(i - map.get(sum - aim), res); // 更新最大长度 i-(map.get(sum-aim)+1)+1
			}
			if (!map.containsKey(sum)) {// 只放和为sum出现的最早位置
				map.put(sum, i);
			}
		}

		return res;

	}

再次改进升级 

若此不仅只有0和1  还有其他数  求0和1数目相等的最大子数组的长度

依然简单 可以将0变为-1  其他数字变为0  还是成了求累加和为0的题了

public static int maxLengthIn01(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] == 0) {                    //0变为1
				arr[i] = -1;
			}else if(arr[i]!=0&&arr[i]!=1){       //其他数变为0
                arr[i] = 0;
           }
		}
		int res = maxLength(arr, 0);
		return res;
	}

	public static int maxLength(int[] arr, int aim) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		// key 某个累加和sum value 这个累加和最早出现的次数
		// 取以每个位置为结尾的等于定值的子数组的最大长度的最大值
		HashMap<Integer, Integer> map = new HashMap<>();
		map.put(0, -1); // 非常重要 意思是累加和为0 最早出现的位置为 -1 默认
		int res = 0;
		int sum = 0; // 前缀和 到i位置
		for (int i = 0; i < arr.length; i++) {
			sum += arr[i]; // arr[0..i]的和 到当前位置的累加和
			if (map.containsKey(sum - aim)) { // 能找到sum-aim出现的最早位置
				// i-map.get(sum-aim)：用当前位置（和为sum）-sum-aim出现的最早位置 则剩下的和为aim
				res = Math.max(i - map.get(sum - aim), res); // 更新最大长度 i-(map.get(sum-aim)+1)+1
			}
			if (!map.containsKey(sum)) {// 只放和为sum出现的最早位置
				map.put(sum, i);
			}
		}
		return res;

	}