题目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
}
