三数之和 leetcode15
知识补充：
map的key值必须是可以比较运算的类型，不可以是函数、map、slice
map记录 失败！超出限制
//得到结果后再去重 失败！
func threeSum(nums []int) [][]int {
L := len(nums)
var intT string
result := [][]int{
}
N := map[int]int{
}
G := map[string]int{
}
table := make([][]int, L)
for i, _ := range table {
table[i] = make([]int, L)
}
for i, v := range nums {
N[v] = i
}
for i := 0; i < L-1; i++ {
for c := i + 1; c < L; c++ {
table[i][c] = nums[i] + nums[c]
if index, ok := N[-table[i][c]]; ok {
if index != i && index != c {
order := []int{
nums[i], nums[c], nums[index]}
slices.Sort(order)
for _, v := range order {
intT = fmt.Sprintf(intT, string(rune(v)))
}
if _, cont := G[intT]; !cont {
result = append(result, []int{
nums[i], nums[c], nums[index]})
}
G[intT] = 1
intT = ""
}
}
}
}
// fmt.Print(table)
return result
}
双指针法
拿这个nums数组来举例，首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。
依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right]。
接下来如何移动left 和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。
如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。
// 自我救赎的双指针法
func threeSum(nums []int) [][]int {
slices.Sort(nums)
L := len(nums)
record := [][]int{
}
//第一个数
for i, i2 := range nums[:L-2] {
//左指针为第二个数，右指针为第三个数。左指针每次从第一个数后一个开始，右指针则从最末尾开始
left, right := i+1, L-1
//第一个数的去重 ，如{-1 -1 0 1}，[0,2,3]和[1,2,3]都满足要求，但是其数组都为[-1,0,1]应该去除之一。所以说当检测当本次循环与上次一致的话，直接跳过
if i > 0 && i2 == nums[i-1] {
continue
}
//循环的结束条件为左指针与右指针重合，即第二个数和第三个数序号一致
for left < right {
if i2+nums[left]+nums[right] == 0 {
record = append(record, []int{
i2, nums[left], nums[right]})
left++
right--
//对第二个数进行去重
for nums[left] == nums[left-1] && left < L-1 {
left++
}
//对第三个数进行去重
for nums[right] == nums[right+1] && right > 1 {
right--
}
}
if i2+nums[left]+nums[right] > 0 {
right--
}
if i2+nums[left]+nums[right] < 0 {
left++
}
}
}
return record
}
四数之和 leetcode18
与三数之和思路大体相同，代码如下：
// 自我救赎的双指针法
func fourSum(nums []int, target int) [][]int {
slices.Sort(nums)
L := len(nums)
if L < 4 {
return nil
}
record := [][]int{
}
//第一个数
for i, val := range nums[:L-3] {
if i > 0 && val == nums[i-1] {
continue
}
//第二个数
for i2 := i + 1; i2 < L-2; i2++ {
val2 := nums[i2]
//左指针为第二个数，右指针为第三个数。左指针每次从第一个数后一个开始，右指针则从最末尾开始
left, right := i2+1, L-1
//第一个数的去重 ，如{-1 -1 0 1}，[0,2,3]和[1,2,3]都满足要求，但是其数组都为[-1,0,1]应该去除之一。所以说当检测当本次循环与上次一致的话，直接跳过
if i2 > i+1 && val2 == nums[i2-1] {
continue
}
//循环的结束条件为左指针与右指针重合，即第二个数和第三个数序号一致
for left < right {
if val+val2+nums[left]+nums[right] == target {
record = append(record, []int{
val, val2, nums[left], nums[right]})
left++
right--
//对第二个数进行去重
for nums[left] == nums[left-1] && left < L-2 {
left++
}
//对第三个数进行去重
for nums[right] == nums[right+1] && right > 2 {
right--
}
}
if val+val2+nums[left]+nums[right] > target {
right--
}
if val+val2+nums[left]+nums[right] < target {
left++
}
}
}
}
return record
}
