18.md

title	date
18. 四数之和	2020-02-04T00:14:00.000Z

https://leetcode-cn.com/problems/4sum/

暴力法：

func fourSum(nums []int, target int) [][]int {
    var res [][]int
    for i, num1 := range nums {
        if len(nums) - i - 1 < 3 {
            return res
        }
        for j, num2 := range nums[i+1:] {
            if len(nums) - i - 1 - j - 1 < 2 {
                continue
            }
            for k, num3 := range nums[i+1+j+1:] {
                if len(nums) - i - 1 - j - 1 - k - 1 < 1 {
                    continue
                }
                for _, num4 := range nums[i+1+j+1+k+1:] {
                    if num1 + num2 + num3 + num4 == target {
                        res = append(res, []int{num1, num2, num3, num4})
                    }
                }
            }
        }
    }
    return res
}

用暴力法可以简单直接的解决问题，时间复杂度 O(n^4)。另外上面的解法中缺失了去重的逻辑，应该需要再增加个 map 结构来检查是否已经有该解。

双指针法：

import "sort"


func fourSum(nums []int, target int) [][]int {
    sort.Ints(nums)
    var res [][]int
    if len(nums) < 4 {
        return res
    }


    for i, num1 := range nums[:len(nums) - 3] {
        // 确保第一个数不重复
        if i > 0 && num1 == nums[i - 1] {
            continue
        }
        for j, num2 := range nums[i+1:len(nums)-2] {
            // 确保第二个数不重复
            if j > 0 && num2 == nums[i+1+j-1] {
                continue
            }


            x := i+1+j+1
            y := len(nums)-1


            for x < y {
                if num1 + num2 + nums[x] + nums[y] < target {
                    x++
                } else if num1 + num2 + nums[x] + nums[y] > target {
                    y--
                } else {
                    res = append(res, []int{num1, num2, nums[x], nums[y]})


                    for x < y && nums[x+1] == nums[x] {
                        // 确保第三个数不重复
                        x++
                    }
                    for x < y && nums[y-1] == nums[y] {
                        // 确保第四个数不重复
                        y--
                    }
                    // 开始计算下个不同的第三个数和第四个数
                    x++
                    y--
                }
            }
        }
    }


    return res
}

时间复杂度：O(n^3)。num1 和 num2 的遍历是 n^2 ，而第三个数和第四个数是通过双指针的方式在一次循环中遍历完成的，因此时间复杂度为 O(n^3)。不过这里忽略了排序的时间复杂度。