题目1

leetcode454:https://leetcode-cn.com/problems/4sum-ii
给你四个整数数组 nums1、nums2、nums3 和 nums4 ,数组长度都是 n ,请你计算有多少个元组 (i, j, k, l) 能满足:

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
输入:nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出:2
解释:
两个元组如下:
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

题解与分析

这道题是哈希法的典型题目
这道题没做出来:
如果暴力解法的话,时间复杂度太高了

题解:

  • 先定义map,存放nums1[i] + nums2[j]每个元素加和和出现次数,
  • 定义变量,统计满足条件次数
  • 遍历nums3[k] + nums4[l]数组,看0-c-d的值是否在map存在,存在的话看看次数是几,并加到count,如果不存在,map虽然添加了键值,但value为0
func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
    count := 0
    m := map[int]int{}
    for _, x1:=range nums1{
        for _,x2:=range nums2{
            m[x1+x2]++
        }
    }
    //遍历nums3[k] + nums4[l]数组,看0-c-d的值是否在map存在,存在的话看看次数是几,并加到count,如果不存在,map虽然添加了键值,但value为0
    for _,x3:=range nums3{
        for _,x4:=range nums4{
            /*if v,ok:=m[-x3-x4];ok{
                count+=v
            }*/
            count += m[-x3-x4]
        }
    }
    return count
}

题目2

三数之和
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。

注意:答案中不可以包含重复的三元组。

题解与分析

这道题我本来先用hash法来做,没通过,里面的几个难点, go没有给数组增加去重的方法也没有set,我的想法是每次把一个切片存到要返回的res里时记录一下,或者最后对res去重,记录的话一开始想把切片当做map的key,这样不行,虽然最后靠排序然后toString来记录,但提交的时候bug很多,里面要考虑的细节太多,就没在用这个方法
这道题用双指针法比较好:

  • 首先将数组排序,然后最外面有一层for循环,i从下标0开始,同时定义一个下标left 在i+1的位置上,定义下标right 在数组结尾的位置上。left, right := i+1, len(nums)-1
  • 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了,因为数组是排序后了,所以right下标就应该向左移动,这样才能让三数之和小一些。
  • 如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了,left 就向右移动,才能让三数之和大一些,直到left与right相遇为止。
func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    res := [][]int{}
    if len(nums)<3{
        return res
    }

    for i := 0; i<len(nums)-2;i++{
        n1 := nums[i]
        // 如果当前索引位置已经大于0了,由于排好序的数组,所以不留情面直接退出
        if n1>0{
            break
        }
        // 判断当前的nums[i]是不是和前一个一样,一样的话就continue,避免重蹈覆辙。
        if i>0&&n1==nums[i-1]{
            continue
        }
        left, right := i+1, len(nums)-1
        for left<right{
            total := nums[i] + nums[left] + nums[right]
            n2, n3 := nums[left], nums[right]
            if total==0{
                // fmt.Println(tmp)
                res = append(res, []int{n1, n2, n3})
                // 这里的判断很重要,即使total==0,也要判断,将left,right移位,否则死循环
                for left<right&&nums[left] == n2{
                    left++
                }
                for left<right&&nums[right]==n3{
                    right--
                }
            }else if total>0{
                right --
            }else{
                left++
            }
        }
    }
    return res
}

题目三

leetcode: 18四数之和

题解与分析

上一道是三数之和,这道题,四数之和, 其实就是在三数之和的基础上套了一层for, 依旧用双指针来把原本暴力O(n^4)的解法,降为O(n^3)的解法。
但四数之和这里有几点需要注意,三数之和目标值是0,这道题是target, 还有不能直接根据n1>target直接break,因为可能是负数还有要注意的是,两个嵌套for循环初始值的关系

func fourSum(nums []int, target int) [][]int {
    res := [][]int{}
    if len(nums)<4{
        return res
    }
    sort.Ints(nums)
    // fmt.Println(nums)
    length := len(nums)
    for i := 0; i<length-3;i++{
        n1 := nums[i]
        // 因为可能是负数
        // if n1>target{
        //     break
        // }
        if i>0&&n1==nums[i-1]{
            continue
        }
        for j:=1+i;j<length-2;j++{
            n2 := nums[j]
            // if n2>target{
            //     break
            // }
            if j>1+i&&nums[j-1]==n2{
                continue
            }
            left, right := j+1, length-1
            for left<right{
                n3, n4 := nums[left], nums[right]
                total := n1 + n2 + n3 + n4
                if total == target{
                    // fmt.Println("res:", []int{n1, n2,n3, n4})
                    res = append(res, []int{n1, n2,n3, n4})
                    for left<right&&nums[left]==n3{
                        left++
                    }
                    for left<right&&nums[right]==n4{
                        right--
                    }
                }else if total>target{
                    right--
                }else{
                    left++
                }
            }
        }
    }
    return res
}
分类: 算法

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

ICP备案号: 辽ICP备20003309号