题目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
}
题目三
题解与分析
上一道是三数之和,这道题,四数之和, 其实就是在三数之和的基础上套了一层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
}