16. 最接近的三数之和
2022-07-28 本文已影响0人
邦_
先dfs,好吧。超时= =。。
func threeSumClosest(_ nums: [Int], _ target: Int) -> Int {
var tempArray:[Int] = []
var ans = 0
var sum = 0
var minDecount = Int.max
let sortNums = nums.sorted()
dfs(0,sortNums,target,sortNums.count,0,&minDecount,&tempArray,&ans,&sum)
return ans
}
func dfs(_ index:Int, _ sortNums:[Int],_ target:Int,_ len:Int,_ begin:Int,_ minDecount:inout Int,_ tempArray: inout [Int],_ ans: inout Int,_ sum:inout Int){
if index == 3 {
var tempDecount = 0
if sum > target {
tempDecount = sum - target
}
else {
tempDecount = target - sum
}
if tempDecount < minDecount {
minDecount = tempDecount
ans = sum
}
return
}
//每一层可以选择的
for i in begin..<len {
let num = sortNums[i]
sum += num
tempArray.append(num)
dfs(index + 1,sortNums.sorted(),target,len,i + 1,&minDecount,&tempArray,&ans,&sum)
sum -= tempArray.removeLast()
}
}
开始三指针= =。。
func threeSumClosest(_ nums: [Int], _ target: Int) -> Int {
let sortNums = nums.sorted()
let len = sortNums.count
var ans = 0
var sum = 0
var decount = Int.max
var c = 1,r = len - 1
for i in 0..<len - 2 {
let num1 = sortNums[i]
if i > 0 && num1 == sortNums[i - 1] {
continue
}
c = i + 1
r = len - 1
while c < r {
let num2 = sortNums[c]
let num3 = sortNums[r]
sum = num1 + num2 + num3
if sum == target {
return sum
}
var tempDecount = 0
if sum > target {
tempDecount = sum - target
r -= 1
while c < r && sortNums[r] == sortNums [r - 1] {
r -= 1
}
}else {
tempDecount = target - sum
c += 1
while c < r && sortNums[c] == sortNums [c + 1] {
c += 1
}
}
//说明差值比较小
if tempDecount < decount {
decount = tempDecount
ans = sum
}
}
}
return ans
}
