Golang 三数之和+ 四数之和 leetcode15、18 双指针法

三数之和 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
}