LeetCode - 18. 4Sum

链接: https://leetcode-cn.com/problems/4sum/
难度: medium

4数之和，暴力解法。

func fourSum(nums []int, target int) [][]int {
    var res = [][]int{}
    length := len(nums)
    if length < 4 {
        return res
    }
    sort.Sort(sort.IntSlice(nums))
    if nums[length - 1] + nums[length-2] + nums[length-3] + nums[length-4] < target || nums[0] + nums[1] + nums[2] + nums[3] > target {
        return res
    }

    for i := 0; i < length - 3; i ++ {
        for j := i + 1; j < length - 2; j ++ {
            for k := j + 1; k < length - 1; k ++ {
                for x := k + 1; x < length; x ++ {
                    if nums[i] + nums[j] + nums[k] + nums[x] == target {
                        sol := []int {nums[i], nums[j], nums[k], nums[x]}
                        if !dup(res, sol) {
                            res = append(res, sol)
                        }
                    }
                }
            }
        }
    }
    return res
}

func dup(res [][]int, arr2 []int) bool {
    for _, arr1 := range res {
        same := true
        for i := 0; i < len(arr1); i ++ {
            if arr1[i] != arr2[i] {
                same = false
                break
            }
        }
        if same {
            return true
        }
    }

    return false
}

执行用时 :112 ms, 在所有 Go 提交中击败了7.67%的用户
内存消耗 :2.8 MB, 在所有 Go 提交中击败了100.00%的用户