一、题目原型：
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
二、题目意思剖析：
最接近其实可以转化为，(三数之和 - target)的绝对值最小。
result = |三数之和 - target|，只需要找出最小的result即可。
result理论上最小值为0，即和target相等
三、解题思路：
最简单的是三层遍历。这里就不说了，复杂度太高。不过也通过了leetcode检测。耗时400ms，超过百分之11的提交记录。
其实我们可以将其简化为 和 上一题15. 三数之和一样的模式上。
也就是将最前面的数字抽出来，然后让left指针和right指针在该数字之后的数组里进行滑动。找出三数之和 - target的绝对值的最小值即可。判断会有点多。。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
func threeSumClosest(_ nums: [Int], _ target: Int) -> Int {
if(nums.count < 3){
var result = 0
for value in nums {
result = result + value
}
return result;
}
var tempNums = nums.sorted{$0<$1}
let count = tempNums.count
var threeSum = tempNums[0] + tempNums[1] + tempNums[2]
print(tempNums)
for indexF in 0 ..< count {
if (indexF != 0) && (tempNums[indexF] == tempNums[indexF - 1]){
continue
}
let tempArray = self.aFunction(numbers: tempNums, begin: indexF + 1, end: count)
print(tempArray)
var left:Int = 0
var right:Int = tempArray.count - 1
while left < right {
print(threeSum)
let newOffsetValue = tempArray[left] + tempArray[right] + tempNums[indexF] - target
if(newOffsetValue == 0){
return target;
}
let result = threeSum - target
if(result < 0){
if(newOffsetValue < 0){
if(newOffsetValue > result){
threeSum = newOffsetValue + target
}
left = left + 1
}else{
if(newOffsetValue < abs(result)){
threeSum = newOffsetValue + target
}
right = right - 1
}
}else{
if(newOffsetValue < 0){
if(abs(newOffsetValue) < result){
threeSum = newOffsetValue + target
}
left = left + 1
}else{
if(newOffsetValue < result){
threeSum = newOffsetValue + target
}
right = right - 1
}
}
}
}
return threeSum
}
|
四、小结
耗时40毫秒，超过77.78%的提交记录，总提交数125。
有其他好的方法请极速留言，非常乐意一起探讨。😄!
近期评论