【无标题】

[算法] 剑指offer2 golang 0和1个数相同的子数组

题目1:

思路1: 暴力

//思路1: 暴力
//将0当作-1看待,
//固定一个,计算后面的位数是否总和位0,计算最大的个数,
//O(n3),优化下计算时间复杂度O(n2)

代码1

func findMaxLength(nums []int) int {
    
    //返回最长的子数组的长度
    //start :19.11
    //思路1: 暴力
    //将0当作-1看待,
    //固定一个,计算后面的位数是否总和位0,计算最大的个数,
    //O(n3),优化下计算时间复杂度O(n2)

    //参数处理
    if len(nums) == 0 {
    
        return 0
    }

    //暴力
    max := 0
    for i := 0; i < len(nums) - 1; i++ {
    
        //左指针
        sum := 1
        if nums[i] == 0 {
    
            sum = -1
        }
        for j := i+1; j < len(nums); j++{
    
            if nums[j] == 0 {
    
                sum--
            }else {
    
                sum++
            }
            // 符合条件刷新最大值 max
            temp := j - i  +1
            if sum == 0 && temp > max{
    
                max = temp
            }
        }
    }
    return max 
}

测试1

思路2: hashmap

//1.使用 hashmap[sum]index 记录前 n 个元素和位 sum 的下标,如果后面的元素 sum2
//如果 sum2 - sum1 = 0, sum2 = sum1,证明存在就取之前的 value 

代码2:

func findMaxLength(nums []int) int {
    
    //返回最长的子数组的长度
    //start :19.26
    //思路2: hashmap
    //1.使用 hashmap[sum]index 记录前 n 个元素和位 sum 的下标,如果后面的元素 sum2
    //如果 sum2 - sum1 = 0, sum2 = sum1,证明存在就取之前的 value 
    if len(nums) == 0 {
    
        return 0
    }

    //1.hashmap 赋值
    hashmap := make(map[int]int)
    //处理边界
    hashmap[0] = -1
    sum1,max := 0,0
    for i := 0; i < len(nums); i++ {
    
        if nums[i] == 0 {
    
            sum1 --
        }else {
    
            sum1 ++
        }
        if val,ok := hashmap[sum1]; ok {
    
            length := i - val 
            if length > max {
    
                max = length
            }
        }else {
    
            //只是保留小index的,大的不需要
            hashmap[sum1] = i
        }
    }
    return max 
}