想到的dfs。。 内存也不占优势，速度也不占优势= =。还好没超时
func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
var sum = 0
let len = nums.count
let sortNums = nums.sorted()
var tempArray = Array.init(repeating: 0, count: 4)
var ans = [[Int]]()
dfs(0,0,target,&sum,len,sortNums,&tempArray,&ans)
return ans
}
func dfs(_ index:Int, _ begin:Int,_ target:Int,_ sum:inout Int,_ len: Int,_ sortNums:[Int],_ tempArray:inout [Int],_ ans: inout [[Int]]){
if index == 4 {
if sum == target {
ans.append(tempArray)
}
return
}
for i in begin..<len {
let num = sortNums[i]
if i > begin && num == sortNums[i - 1] {
continue
}
tempArray[index] = num
sum += num
dfs(index + 1, i + 1,target,&sum,len,sortNums,&tempArray,&ans)
sum -= num
}
}
仿照三数之和。。
func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
let len = nums.count
if len < 4 {
return []
}
let sortNums = nums.sorted()
var ans = [[Int]]()
var index2 = 0, index3 = 0 ,index4 = 0
let indexLast = len - 4
let index2Last = len - 3
// let index3Last = len - 2
let index4Last = len - 1
for i in 0...indexLast{
index2 = i + 1
let num1 = sortNums[i]
// //过滤掉第一层重复的数字
if i > 0 && num1 == sortNums[i - 1] {
continue
}
for j in index2...index2Last {
let num2 = sortNums[j]
index3 = j + 1
//过滤第二层重复的
if j > index2 && num2 == sortNums[j - 1] {
continue
}
index4 = index4Last
while index3 < index4 {
let num3 = sortNums[index3]
let num4 = sortNums[index4]
let sum = num1 + num2 + num3 + num4
//遇到符合条件的
if sum == target {
ans.append([num1,num2,num3,num4])
while index3 < index4 && num3 == sortNums[index3 + 1] {
index3 += 1
continue
}
while index3 < index4 && num4 == sortNums[index4 - 1] {
index4 -= 1
continue
}
index3 += 1
index4 -= 1
}else if sum < target {
index3 += 1
}else {
index4 -= 1
}
}
}
}
return ans
}
然后优化版本，当排序之后。。最小的都大于target的时候 就可以不用往下走了。。因为后边的组合只会更大
func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
let len = nums.count
if len < 4 {
return []
}
let sortNums = nums.sorted()
var ans = [[Int]]()
var index2 = 0, index3 = 0 ,index4 = 0
let indexLast = len - 4
let index2Last = len - 3
let index4Last = len - 1
for i in 0...indexLast{
index2 = i + 1
let num1 = sortNums[i]
// //过滤掉第一层重复的数字
if i > 0 && num1 == sortNums[i - 1] {
continue
}
if num1 + sortNums[i + 1] + sortNums[i + 2] + sortNums[i + 3] > target {
break
}
for j in index2...index2Last {
let num2 = sortNums[j]
index3 = j + 1
//过滤第二层重复的
if j > index2 && num2 == sortNums[j - 1] {
continue
}
if num1 + num2 + sortNums[j + 1] + sortNums[j + 2] > target {
break
}
index4 = index4Last
while index3 < index4 {
let num3 = sortNums[index3]
let num4 = sortNums[index4]
let sum = num1 + num2 + num3 + num4
//遇到符合条件的
if sum == target {
ans.append([num1,num2,num3,num4])
while index3 < index4 && num3 == sortNums[index3 + 1] {
index3 += 1
continue
}
while index3 < index4 && num4 == sortNums[index4 - 1] {
index4 -= 1
continue
}
index3 += 1
index4 -= 1
}else if sum < target {
index3 += 1
}else {
index4 -= 1
}
}
}
}
return ans
}
网友评论