教程

两数之和 三数之和【基础算法精讲 02】_哔哩哔哩_bilibili
一个方法团灭 nSum 问题 :: labuladong的算法小抄

题目

两数之和

力扣-1-两数之和

hash表
1
2
3
4
5
6
7
8
9
10
11
12
13
func twoSum(nums []int, target int) []int {
    numsMap := make(map[int]int, 0)

    for i, v := range nums {
        if index, ok := numsMap[target-v]; ok {
            return []int{index, i}
        }

        numsMap[v] = i
    }

    return nil
}
暴力破解双遍历
1
2
3
4
5
6
7
8
9
10
11
func twoSum(nums []int, target int) []int {
    for i := 0; i< len(nums); i++ {
        for j := i+1; j<len(nums); j++ {
            if nums[i] + nums[j] == target {
                return []int{i, j}
            }
        }
    }

    return nil
}

三数之和

力扣-15-三数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
func threeSum(nums []int) [][]int {
    // 排序
    sort.Ints(nums)
    // 保存结果
    res := make([][]int, 0)
    // 数组长度
    n := len(nums)

    // 这里为什么-2？
    // 因为这是有序数组，如果有复合条件的结果[下表i,j,k]必然是i<j<k， 所以需要给j, k预留位置
    for i := 0; i < n-2; i++ {
        // 首先nums是有序数组
        // 如果某一列中最小的两个数之和加起来都大于0，则说明和其余的数加起来必然大于0
        if i > 0 && nums[i]+nums[i-1] > 0 {
            break
        }

        // 元素相同，避免重复，则跳过
        if i>0 && nums[i] == nums[i-1] {
            continue
        }

        j := i+1 // 中间位置
        k := n-1 // 最大值的位置，即最右边的位置
        for j < k {
            sum := nums[i]+nums[j]+nums[k]

            if sum == 0 {
                res = append(res, []int{nums[i], nums[j], nums[k]})

                // 还需要排除重复的
                j++
                for j < k && nums[j]==nums[j-1] {
                    j++
                }

                k--
                for j < k && nums[k] == nums[k+1] {
                    k--
                }
            }
            
            if sum < 0 {
                // 小于0， 则说明中间值太小了，j需要往右边移动
                j++
            }

            if sum > 0 {
                // 大于0，则说明中间值太大了，需要将最右边的k往左边移动
                k--
            }
        }
    }

    return res
}

四数之和

力扣-18-四数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// 其实和三数之和是一个意思，就是先固定第一个数，然后三个数按照三数之和来处理
func fourSum(nums []int, target int) [][]int {
    if len(nums) < 4 {
        return nil
    }
    sort.Ints(nums)

    res := make([][]int, 0)
    for i :=0; i<len(nums)-3; i++ {
        if i > 0 && nums[i-1] == nums[i] {
            continue
        }
 
        for j := i+1; j<len(nums)-2; j++ {
            if j>i+1 && nums[j] == nums[j-1] {
                continue
            }

            k := j+1
            r := len(nums)-1

            for k < r {
                sum := nums[i]+nums[j]+nums[k]+nums[r]
                if sum < target {
                    k++
                }

                if sum  > target {
                    r--
                }

                if sum == target {
                    res = append(res, []int{nums[i],nums[j],nums[k],nums[r]})
                    k++
                    for k < r && nums[k]==nums[k-1] {
                        k++    
                    }
                    r--
                     for k < r && nums[r]==nums[r+1] {
                        r--    
                    }
                }
            }

        }
    }

    return res
}