题目：4Sum

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

找到数组中，相加等于某个target的4个数的所有组合

思路

本题和2sum，3sum都是同一个类型的，直接想到的就是在3sum的方案外再加一层循环，试了一下居然MLE，最后用4重循环搞定

code

func fourSum(nums []int, target int) [][]int { var ret [][]int sort.Ints(nums) val := [...]int{0, 0, 0} for i := 0; i < len(nums); i++ { if i > 0 && nums[i-1] == nums[i] { continue } for j := i + 1; j < len(nums); j++ { val[0] = nums[i] + nums[j] if val[0] > target && nums[j] > 0 { //后面不可能有解 break } if j > i+1 && nums[j-1] == nums[j] { //相同元素 continue } for k := j + 1; k < len(nums); k++ { val[1] = val[0] + nums[k] if val[1] > target && nums[k] > 0 { break } if k > j+1 && nums[k-1] == nums[k] { continue } for m := k + 1; m < len(nums); m++ { val[2] = val[1] + nums[m] if val[2] == target { tmp := []int{nums[i], nums[j], nums[k], nums[m]} ret = append(ret, tmp) break } if val[2] > target { break } } } } } return ret}

更多内容请移步我的repo：
https://github.com/anakin/golang-leetcode