摘要

最接近的三数之和查找器实现了在数组中找到三个数，使得它们的和最接近目标值的功能。本文详细解析了输入解析、排序+双指针法、差值计算、过程分析等核心功能的代码实现细节。

1. 算法背景

1.1 问题描述

给定一个整数数组和一个目标值，找出数组中三个数的和，使得这个和最接近目标值。

示例：

• 数组：[-1, 2, 1, -4]
• 目标值：1
• 结果：2（由 -1 + 2 + 1 = 2 构成，与目标值 1 的差为 1）

1.2 应用场景

• 近似匹配
• 优化问题
• 最接近值查找
• 算法竞赛

2. 核心算法原理

2.1 排序+双指针法

先对数组排序，然后固定第一个数，使用双指针在剩余部分查找两数之和。根据当前和与目标值的关系移动指针，实时更新最接近的和。

2.2 差值跟踪

跟踪当前和与目标值的差值，始终保持记录最小差值对应的和。

3. 代码实现详细解析

3.1 输入解析模块

var nums: List<Int>? = null
var target = 0

payload.lines()
    .map { it.trim() }
    .filter { it.isNotEmpty() }
    .forEach { line ->
        when {
            line.startsWith("nums=", ignoreCase = true) -> {
                val valuesStr = line.substringAfter("=").trim()
                try {
                    nums = valuesStr.split(",")
                        .map { it.trim() }
                        .filter { it.isNotEmpty() }
                        .map { it.toInt() }
                } catch (e: Exception) {
                    nums = null
                }
            }
            line.startsWith("target=", ignoreCase = true) -> {
                try {
                    target = line.substringAfter("=").trim().toInt()
                } catch (e: Exception) {
                    target = 0
                }
            }
        }
    }

代码解析：

这段代码实现了灵活的输入解析机制，支持从输入字符串中提取数组和目标值。首先声明两个变量：nums 是一个可空整数列表，用于存储解析后的数组；target 是目标值，初始值为 0。

然后使用函数式编程风格处理输入：payload.lines() 将输入按行分割，map { it.trim() } 去除每行的首尾空白字符，filter { it.isNotEmpty() } 过滤空行。

在 forEach 循环中，使用 when 表达式进行模式匹配。第一个分支处理 nums= 格式的输入：提取等号后面的部分作为数组字符串，然后使用 split(",") 按逗号分割，map { it.trim() } 去除空白字符，filter { it.isNotEmpty() } 过滤空元素，map { it.toInt() } 转换为整数。使用 try-catch 块捕获可能的异常，确保程序的健壮性。

第二个分支处理 target= 格式的输入：提取等号后面的部分并转换为整数。如果解析失败，保持目标值为 0。

3.2 排序+双指针法实现

fun threeSumClosestSortedTwoPointer(nums: List<Int>, target: Int): Pair<Int, List<Int>> {
    val sorted = nums.sorted()
    val n = sorted.size
    var closestSum = sorted[0] + sorted[1] + sorted[2]
    var minDiff = kotlin.math.abs(closestSum - target)
    val bestTriplet = mutableListOf<Int>()

    for (i in 0 until n - 2) {
        var left = i + 1
        var right = n - 1

        while (left < right) {
            val sum = sorted[i] + sorted[left] + sorted[right]
            val diff = kotlin.math.abs(sum - target)

            if (diff < minDiff) {
                minDiff = diff
                closestSum = sum
                bestTriplet.clear()
                bestTriplet.addAll(listOf(sorted[i], sorted[left], sorted[right]))
            }

            when {
                sum < target -> left++
                else -> right--
            }
        }
    }

    return Pair(closestSum, bestTriplet)
}

代码解析：

这是排序+双指针法的核心实现，通过排序和双指针技术高效地查找最接近目标值的三数之和。函数首先对输入数组进行排序，使用 sorted() 方法创建一个新的排序后的列表。排序是算法的关键预处理步骤，使得双指针法成为可能。

然后获取数组长度 n，初始化最接近的和为前三个数的和（closestSum = sorted[0] + sorted[1] + sorted[2]），这是算法的初始候选值。初始化最小差值为初始和与目标值的差的绝对值（minDiff = kotlin.math.abs(closestSum - target)），使用 kotlin.math.abs 计算绝对值。

创建一个可变列表 bestTriplet 用于存储最接近和对应的三个数，初始为空列表，后续会更新。

接下来使用外层循环固定第一个数。循环变量 i 从 0 开始，到 n - 2 结束（因为需要至少三个数，所以最后一个数的索引最多为 n - 3）。

然后初始化双指针：left 指向 i + 1（第二个数的起始位置），right 指向 n - 1（最后一个数的位置）。

接下来使用内层 while 循环，条件是 left < right，即两个指针还没有相遇。在循环内部，首先计算三个数的和：sum = sorted[i] + sorted[left] + sorted[right]。

然后计算当前和与目标值的差的绝对值：diff = kotlin.math.abs(sum - target)。这个差值表示当前和与目标值的接近程度，差值越小，说明越接近目标值。

然后检查当前差值是否小于记录的最小差值。如果小于（diff < minDiff），说明找到了更接近目标值的和。更新最小差值（minDiff = diff），更新最接近的和（closestSum = sum），清空最佳三元组列表并添加当前三个数（bestTriplet.clear() 和 bestTriplet.addAll(...)）。这种实时更新的机制确保了算法能够找到全局最接近的和。

接下来根据当前和与目标值的关系移动指针。使用 when 表达式：

如果 sum < target，说明当前和小于目标值，需要增大和。由于数组已排序，将左指针向右移动（left++）可以增大和。

否则（sum >= target），说明当前和大于等于目标值，需要减小和。将右指针向左移动（right--）可以减小和。

这种根据和与目标值的关系移动指针的策略，利用了排序数组的性质，使得算法能够高效地搜索所有可能的三数组合，找到最接近目标值的和。

外层循环结束后，返回最接近的和和对应的三元组，使用 Pair 封装两个返回值。

这个算法的时间复杂度是 O(n²)，因为外层循环 O(n)，内层双指针循环在最坏情况下也是 O(n)。空间复杂度是 O(1)，除了存储结果，只使用了固定数量的变量。

3.3 差值计算和更新机制

val diff = kotlin.math.abs(sum - target)

if (diff < minDiff) {
    minDiff = diff
    closestSum = sum
    bestTriplet.clear()
    bestTriplet.addAll(listOf(sorted[i], sorted[left], sorted[right]))
}

代码解析：

这段代码实现了差值计算和更新机制，是算法的核心部分。首先计算当前和与目标值的差的绝对值，使用 kotlin.math.abs(sum - target)。绝对值表示距离，差值越小，说明当前和越接近目标值。

然后检查当前差值是否小于记录的最小差值。如果小于，说明找到了更接近目标值的和，需要更新记录。更新最小差值为当前差值，更新最接近的和为当前和，清空最佳三元组列表并添加当前的三个数。

这种实时更新的机制确保了算法在遍历所有可能的三数组合时，始终保持记录最接近目标值的和。与精确匹配的三数之和问题不同，这个问题不需要去重，但需要跟踪最小差值，因为可能存在多个和与目标值差值相同的情况。

3.4 指针移动策略

when {
    sum < target -> left++
    else -> right--
}

代码解析：

这段代码实现了指针移动策略，根据当前和与目标值的关系决定移动哪个指针。如果当前和小于目标值（sum < target），说明需要增大和。由于数组已排序，增大和的方法是移动左指针向右（left++），因为右边的元素更大。

如果当前和大于等于目标值（sum >= target），说明需要减小和。减小和的方法是移动右指针向左（right--），因为左边的元素更小。

这种策略利用了排序数组的性质，使得算法能够系统性地搜索所有可能的三数组合，通过逐步逼近的方式找到最接近目标值的和。这种贪心策略保证了算法的高效性，时间复杂度从暴力法的 O(n³) 降低到 O(n²)。

4. 算法复杂度分析

4.1 时间复杂度

• 排序+双指针法：O(n²)，外层循环 O(n)，内层双指针 O(n)
• 暴力法：O(n³)，需要检查所有可能的三元组
• 总体时间复杂度：O(n²)（使用排序+双指针法）

4.2 空间复杂度

• 排序+双指针法：O(1)，除了存储结果，只使用固定数量的变量
• 暴力法：O(1)，只使用固定数量的变量
• 总体空间复杂度：O(1)

5. 算法优化建议

5.1 排序+双指针法优化

排序+双指针法已经是时间最优的算法，时间复杂度为 O(n²)。

5.2 提前终止优化

如果找到差值为 0 的和（完全匹配），可以提前终止，但在最坏情况下仍然需要遍历所有可能。

5.3 初始值优化

当前使用前三个数的和作为初始值，这是一种合理的初始化方式。

6. 应用场景扩展

1. 近似匹配：在数据中查找最接近目标值的组合
2. 优化问题：各种需要寻找最接近解的优化问题
3. 最接近值查找：在数值范围内查找最接近的值
4. 算法竞赛：LeetCode 等平台的经典问题
5. 扩展问题：最接近的 K 数之和等变体

7. 总结

最接近的三数之和查找器实现了高效的查找算法，核心要点：

1. 排序+双指针法：时间复杂度 O(n²)，先排序再使用双指针查找
2. 差值跟踪：实时跟踪最小差值，更新最接近的和
3. 指针移动策略：根据当前和与目标值的关系移动指针
4. 实时更新机制：在遍历过程中始终保持记录最接近目标值的和

通过深入理解代码实现，可以更好地应用这个算法解决实际问题，如近似匹配、优化问题、最接近值查找等场景。排序+双指针法和差值跟踪的思想也可以扩展到最接近的 K 数之和等类似问题中。

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.csdn.net