代码随想录算法训练营第七天 | 454、383、15、18

算法
, , ,

454. 四数相加 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package main

func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
    sumAB := make(map[int]int)
    // 计算 A 和 B 所有元素和的频率
    for _, a := range nums1 {
        for _, b := range nums2 {
            sumAB[a+b]++
        }
    }
    count := 0
    // 遍历 C 和 D，查找互补和的次数
    for _, c := range nums3 {
        for _, d := range nums4 {
            count += sumAB[-(c + d)]
        }
    }
    return count
}

383. 赎金信

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package main

func canConstruct(ransomNote string, magazine string) bool {
    if len(ransomNote) > len(magazine) {
        return false
    }
    var counts [26]int
    for _, ch := range magazine {
        counts[ch-'a']++
    }
    for _, ch := range ransomNote {
        index := ch - 'a'
        counts[index]--
        if counts[index] < 0 {
            return false
        }
    }
    return true
}

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
package main

import "sort"

func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    result := [][]int{}
    n := len(nums)
    if n < 3 {
        return result
    }

    for i := 0; i < n-2; i++ {
        // 跳过重复的起始元素
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        // 提前终止条件（当前元素过大）
        if nums[i] > 0 {
            break
        }

        left, right := i+1, n-1
        for left < right {
            sum := nums[i] + nums[left] + nums[right]
            switch {
            case sum == 0:
                result = append(result, []int{nums[i], nums[left], nums[right]})
                // 跳过重复的 left 和 right
                for left < right && nums[left] == nums[left+1] {
                    left++
                }
                for left < right && nums[right] == nums[right-1] {
                    right--
                }
                left++
                right--
            case sum < 0:
                left++
            default:
                right--
            }
        }
    }
    return result
}

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
package main

import "sort"

func fourSum(nums []int, target int) [][]int {
    sort.Ints(nums)
    n := len(nums)
    result := [][]int{}
    if n < 4 {
        return result
    }

    for i := 0; i < n-3; i++ {
        // 跳过重复的 i
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        // 剪枝：当前 i 的最小四数之和已超过 target
        if nums[i]+nums[i+1]+nums[i+2]+nums[i+3] > target {
            break
        }
        // 剪枝：当前 i 的最大四数之和仍不足 target
        if nums[i]+nums[n-3]+nums[n-2]+nums[n-1] < target {
            continue
        }

        for j := i + 1; j < n-2; j++ {
            // 跳过重复的 j
            if j > i+1 && nums[j] == nums[j-1] {
                continue
            }
            // 剪枝：i+j 的最小四数之和已超过 target
            if nums[i]+nums[j]+nums[j+1]+nums[j+2] > target {
                break
            }
            // 剪枝：i+j 的最大四数之和仍不足 target
            if nums[i]+nums[j]+nums[n-2]+nums[n-1] < target {
                continue
            }

            left, right := j+1, n-1
            for left < right {
                sum := nums[i] + nums[j] + nums[left] + nums[right]
                if sum == target {
                    result = append(result, []int{nums[i], nums[j], nums[left], nums[right]})
                    // 跳过重复的 left 和 right
                    for left < right && nums[left] == nums[left+1] {
                        left++
                    }
                    for left < right && nums[right] == nums[right-1] {
                        right--
                    }
                    left++
                    right--
                } else if sum < target {
                    left++
                } else {
                    right--
                }
            }
        }
    }
    return result
}