题目地址

描述

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。

 

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
 

提示：

1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109

思路

排序 + 双指针，能有效的提高遍历效率

本人题解

func fourSum(nums []int, target int) [][]int {
   // 排序
	sort.Slice(nums, func(i, j int) bool {
        return nums[i] < nums[j]
    })

	// 因为是四数之和，所以外边两层要通过遍历完成，内两层通过《排序 + 双指针 解两数之和》思路处理
	list := [][]int{}
	
	uniqueFlagMap := map[string]bool{}
	for i1 := 0; i1 < len(nums); i1++ {
		for i2 := i1 + 1; i2 < len(nums); i2++ {
			if l := twoSum(nums, i2+1, len(nums)-1, target-nums[i1]-nums[i2]); len(l) > 0 {
				for _, item := range l {
					// 因为不能出现重复结果，所以此处做了去重处理
					uniqueFlag := fmt.Sprintf("%d%d%d%d", nums[i1], nums[i2], nums[item[0]], nums[item[1]])
					if !uniqueFlagMap[uniqueFlag] {
						uniqueFlagMap[uniqueFlag] = true
						list = append(list, []int{nums[i1], nums[i2], nums[item[0]], nums[item[1]]})
					}
				}
			}
		}
	}
	return list
}

// 求有序数组两数之和方法
func twoSum(nums []int, i3, i4, target int) [][]int {
	list := [][]int{}
	for i3 < i4 {
		t := nums[i3] + nums[i4]
		if t == target {
			list = append(list, []int{i3, i4})
			i3++
		} else if t > target {
			i4--
		} else {
			i3++
		}
	}
	return list
}

在LeetCode提交后，得分极差

优质解法

然后找了得分靠前的一位大佬的解法，果然牛逼的解法是不走寻常路的，先上代码：

func fourSum(nums []int, target int) [][]int {
    sort.Slice(nums, func(i, j int) bool {
        return nums[i] < nums[j]
    })

    n := len(nums)
    var ans [][]int

    for a := 0; a < n-3; a++ {
        if a > 0 && nums[a] == nums[a-1] {
            continue
        }
        if nums[a] + nums[a+1] + nums[a+2] + nums[a+3] > target {
            break
        }
        if nums[a] + nums[n-1] + nums[n-2] + nums[n-3] < target {
            continue
        }
        for b := a+1; b < n-2; b++ {
            if b > a+1 && nums[b] == nums[b-1] {
                continue
            }
            c := b+1
            d := n-1
            for c < d {
                cur := nums[a] + nums[b] + nums[c] + nums[d]
                if cur == target {
                    ans = append(ans, []int{nums[a], nums[b], nums[c], nums[d]})
                    c += 1
                    d -= 1
                    for c < d && nums[c] == nums[c-1] {
                        c += 1
                    }
                    for c < d && nums[d] == nums[d+1] {
                        d -= 1
                    }
                } else if cur < target {
                    c += 1
                } else {
                    d -= 1
                }
            }
        }
    }

    return ans
}

此代码直接借鉴大佬的，有侵权的地方，联系小编

总结

经过对优质解法的分析，得出了以下几点结论：

1、小编的整体思路是没问题的，也就是 ”排序 + 双指针“
2、优质代码增加了以下几点处理：

• 为了不做去重复处理，在遍历的过程中，就对有可能导致重复的数据做了处理。处理思路是因为数组已经做了排序，所以有可能导致重复结果的数据是挨在一起的，比如 [-1,-1,0,0,-2,-2]，如果对第一个-1已经做了处理，第二个-1就不用做处理了，直接跳过即可

func fourSum(nums []int, target int) [][]int {
    sort.Slice(nums, func(i, j int) bool {
        return nums[i] < nums[j]
    })

    n := len(nums)
    var ans [][]int

    for a := 0; a < n-3; a++ {
    	// 跳过有可能导致重复结果的数据
        if a > 0 && nums[a] == nums[a-1] {
            continue
        }
        if nums[a] + nums[a+1] + nums[a+2] + nums[a+3] > target {
            break
        }
        if nums[a] + nums[n-1] + nums[n-2] + nums[n-3] < target {
            continue
        }
        for b := a+1; b < n-2; b++ {
        	// 跳过有可能导致重复结果的数据
            if b > a+1 && nums[b] == nums[b-1] {
                continue
            }
            c := b+1
            d := n-1
            for c < d {
                cur := nums[a] + nums[b] + nums[c] + nums[d]
                if cur == target {
                    ans = append(ans, []int{nums[a], nums[b], nums[c], nums[d]})
                    c += 1
                    d -= 1
                    // 跳过有可能导致重复结果的数据
                    for c < d && nums[c] == nums[c-1] {
                        c += 1
                    }
                    // 跳过有可能导致重复结果的数据
                    for c < d && nums[d] == nums[d+1] {
                        d -= 1
                    }
                } else if cur < target {
                    c += 1
                } else {
                    d -= 1
                }
            }
        }
    }

    return ans
}

• 对有序数组做掐头去尾处理

 for a := 0; a < n-3; a++ {
	// 去尾处理
	if nums[a]+nums[a+1]+nums[a+2]+nums[a+3] > target {
		break
	}

	// 掐头处理
	if nums[a]+nums[n-1]+nums[n-2]+nums[n-3] < target {
		continue
	}
}

经过这两步的优化，极大程度降低了遍历的次数，同时也缩短了每次遍历的耗时，所以整体上优化了耗时