昆明网络公司网站,2021网页qq登陆,建设网站网,网站建设南宁文章目录 三数之和 leetcode15map记录 失败#xff01;超出限制双指针法 四数之和 leetcode18 三数之和 leetcode15
知识补充#xff1a; map的key值必须是可以比较运算的类型#xff0c;不可以是函数、map、slice map记录 失败#xff01;超出限制
//得到结果后再去重 失… 文章目录 三数之和 leetcode15map记录 失败超出限制双指针法 四数之和 leetcode18 三数之和 leetcode15
知识补充 map的key值必须是可以比较运算的类型不可以是函数、map、slice map记录 失败超出限制
//得到结果后再去重 失败
func threeSum(nums []int) [][]int {L : len(nums)var intT stringresult : [][]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] 1intT }}}}// fmt.Print(table)return result
}双指针法
拿这个nums数组来举例首先将数组排序然后有一层for循环i从下标0的地方开始同时定一个下标left 定义在i1的位置上定义下标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 : i1, 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 i2nums[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[right1] right 1 {
right--
}
}
if i2nums[left]nums[right] 0 {
right--
}
if i2nums[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 : i21, L-1//第一个数的去重 如{-1 -1 0 1}[0,2,3]和[1,2,3]都满足要求但是其数组都为[-1,0,1]应该去除之一。所以说当检测当本次循环与上次一致的话直接跳过
if i2 i1 val2 nums[i2-1] {
continue
}//循环的结束条件为左指针与右指针重合即第二个数和第三个数序号一致
for left right {
if valval2nums[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[right1] right 2 {
right--
}
}
if valval2nums[left]nums[right] target {
right--
}
if valval2nums[left]nums[right] target {
left
}
}}}return record
}
