2021-6-03 连续数组

package Normal;
import java.util.HashMap;
import java.util.Map;
public class ContinuousArray_0_1 {
    public static int findMaxLength(int[] nums) {
        //连续子数组长度
        int maxLength = 0;
        //哈希表
        Map<Integer,Integer> map = new HashMap<Integer, Integer>();
        //计数
        int count = 0;
        //将0和1的连续子数组长度问题，转化为-1和1的元素和问题，0位置的0转为-1
        map.put(count,-1);
        //遍历数组
        for(int i = 0;i<nums.length;i++){
            int num = nums[i];
            //为1则++
            if(num == 1){
                count++;
            }else{//反之则--
                count--;
            }
            //如果map中包含count当前的值，则取出count在哈希表中对应的下标preIndex
            //nums从下标preIndex+1到i的子数组中有相同的0和1
            //该子数组的长度为i-preIndex
            //使用该数组的长度更新最长子数组的长度
            if(map.containsKey(count)){
                //将map中count的值赋给前缀和
                int preIndex = map.get(count);
                maxLength = Math.max(maxLength,i-preIndex);
            }else{//如果count的值不被包含于map中，则将当前余数和当前下标i的值放到map中
                map.put(count,i);
            }
        }
        return maxLength;
    }
    public static void main(String[] args){
        int[] nums = new int[]{0,1,0,1};
        System.out.println(findMaxLength(nums));
    }
}