两数之和查找器 KMP OpenHarmony算法实现

sunjingwen0705

938人浏览 · 2025-12-06 15:08:54

sunjingwen0705 · 2025-12-06 15:08:54 发布

在这里插入图片描述

摘要

两数之和查找器实现了在数组中找到两个数的索引，使得它们的和等于目标值的功能。本文详细解析了输入解析、暴力法、哈希表法、查找过程展示等核心功能的代码实现细节。

1. 算法背景

1.1 问题描述

给定一个整数数组和一个目标值，找出数组中两个数的索引，使得它们的和等于目标值。假设每个输入只对应一个答案，且不能重复使用同一个元素。

示例：

数组：[2, 7, 11, 15]
目标值：9
结果：索引 [0, 1]，因为 2 + 7 = 9

1.2 应用场景

查找配对问题
补数匹配
数据验证
算法竞赛
系统设计中的查找优化

2. 核心算法原理

2.1 暴力法

使用双重循环遍历所有可能的数对，检查它们的和是否等于目标值。时间复杂度 O(n²)，空间复杂度 O(1)。

2.2 哈希表法

使用哈希表存储已遍历的元素和其索引，对于当前元素，检查目标值减去当前元素的差值是否在哈希表中。时间复杂度 O(n)，空间复杂度 O(n)。

3. 代码实现详细解析

3.1 输入解析模块

var arrayStr: String? = null
var target: Int? = null

payload.lines()
    .map { it.trim() }
    .filter { it.isNotEmpty() }
    .forEach { line ->
        when {
            line.startsWith("array=", ignoreCase = true) -> {
                arrayStr = line.substringAfter("=").trim()
            }
            line.startsWith("target=", ignoreCase = true) -> {
                target = line.substringAfter("=").trim().toIntOrNull()
            }
        }
    }

代码解析：

这段代码实现了灵活的输入解析机制，支持从输入字符串中提取数组和目标值。首先声明两个可空变量：arrayStr 用于存储数组的字符串表示，target 用于存储目标值的整数表示。使用可空类型是因为这些参数可能不存在或解析失败，需要后续验证。

然后使用函数式编程风格处理输入：payload.lines() 将输入按行分割，map { it.trim() } 去除每行的首尾空白字符，filter { it.isNotEmpty() } 过滤空行，得到一个干净的字符串列表。这种链式调用是 Kotlin 中常见的处理集合的方式，代码简洁且易于理解。

接下来使用 forEach 遍历每一行，使用 when 表达式进行模式匹配。when 表达式是 Kotlin 中强大的条件判断结构，比传统的 if-else 链更简洁清晰。

第一个分支处理 array= 格式的输入。使用 startsWith("array=", ignoreCase = true) 检查行是否以 “array=” 开头（忽略大小写），如果匹配，使用 substringAfter("=") 提取等号后面的部分作为数组的字符串，trim() 去除空白字符。这种格式支持用户明确指定数组参数。

第二个分支处理 target= 格式的输入，使用相同的方式提取目标值。使用 toIntOrNull() 安全地将字符串转换为整数，如果转换失败返回 null，避免了异常抛出。这种安全转换是 Kotlin 中推荐的做法，使代码更加健壮。

3.2 数组解析和验证

val numbers = arrayStr!!.split(",", ";", " ")
    .map { it.trim() }
    .filter { it.isNotEmpty() }
    .mapNotNull { it.toIntOrNull() }

if (numbers.isEmpty()) {
    return "❌ 无法解析数组，请使用整数格式，如：array=2,7,11,15"
}

代码解析：

这段代码将数组字符串解析为整数列表，并验证解析结果。首先使用 split(",", ";", " ") 按逗号、分号或空格分割字符串。支持多种分隔符提高了灵活性，用户可以输入 2,7,11,15、2;7;11;15 或 2 7 11 15 等格式。

然后使用 map { it.trim() } 去除每个分割后元素的空白字符，确保即使输入中有多余的空格也能正确解析。例如，输入 "2, 7, 11, 15" 会被正确处理。

接下来使用 filter { it.isNotEmpty() } 过滤空字符串。如果在分割后产生空字符串（例如输入 "2,,7"），这些空字符串会被过滤掉，避免解析错误。

然后使用 mapNotNull { it.toIntOrNull() } 将每个字符串转换为整数。toIntOrNull() 安全地将字符串转换为整数，如果转换失败返回 null。mapNotNull 会自动过滤掉 null 值，只保留成功转换的整数。这样即使输入中包含非数字字符，也能部分解析出有效的数字。

最后检查解析后的数组是否为空。如果为空，说明解析失败或输入无效，返回错误信息提示用户使用正确的格式。这种验证确保了后续算法能够正确执行。

3.3 暴力法实现

fun twoSumBruteForce(nums: List<Int>, target: Int): Pair<Int, Int>? {
    for (i in nums.indices) {
        for (j in i + 1 until nums.size) {
            if (nums[i] + nums[j] == target) {
                return Pair(i, j)
            }
        }
    }
    return null
}

代码解析：

这是暴力法的核心实现，使用双重循环遍历所有可能的数对。函数首先使用外层循环遍历数组的所有起始位置，循环变量 i 从 0 开始，使用 nums.indices 获取数组的所有有效索引。

然后使用内层循环遍历从 i + 1 开始的所有后续位置，循环变量 j 从 i + 1 到 nums.size - 1（使用 until 关键字表示不包含右边界）。这种设计确保了每个数对只被检查一次，并且不会重复使用同一个元素（因为 j 始终大于 i）。

在内层循环中，检查当前两个元素的和是否等于目标值。如果 nums[i] + nums[j] == target，说明找到了匹配的数对，立即返回这两个索引组成的 Pair。Pair 是 Kotlin 中用于表示两个值的标准数据结构，这里用于存储两个索引。

如果所有数对都检查完毕但没有找到匹配，函数返回 null，表示不存在满足条件的两个数。这种显式的返回值设计使得调用者可以清楚地知道查找是否成功。

这个算法的时间复杂度是 O(n²)，因为需要检查所有可能的数对，其中 n 是数组的长度。空间复杂度是 O(1)，因为只使用了固定数量的变量，不需要额外的空间。虽然时间复杂度较高，但算法实现简单直观，容易理解和验证。

3.4 哈希表法实现

fun twoSumHashMap(nums: List<Int>, target: Int): Pair<Int, Int>? {
    val map = mutableMapOf<Int, Int>()
    for (i in nums.indices) {
        val complement = target - nums[i]
        if (map.containsKey(complement)) {
            return Pair(map[complement]!!, i)
        }
        map[nums[i]] = i
    }
    return null
}

代码解析：

这是哈希表法的核心实现，通过牺牲空间来换取时间效率。函数首先创建一个可变映射 map，用于存储已遍历的元素和其索引。mutableMapOf<Int, Int>() 创建了一个键值对映射，其中键是数组元素的值，值是该元素的索引。

然后使用单层循环遍历数组的所有元素，循环变量 i 从 0 开始。在循环内部，首先计算当前元素需要的补数（complement），即目标值减去当前元素的值。这个补数就是我们要在已遍历的元素中查找的值。

然后检查补数是否在哈希表中。使用 map.containsKey(complement) 检查映射中是否存在这个键。如果存在，说明之前已经遍历过这个值，并且它对应的索引存储在映射中。此时，我们已经找到了两个数：一个是之前遍历过的元素（索引为 map[complement]!!），一个是当前元素（索引为 i）。立即返回这两个索引组成的 Pair。

注意这里使用 !! 非空断言操作符，因为我们已经在 containsKey 检查中确认了键的存在，所以可以安全地断言值不为 null。这种设计避免了额外的空值检查。

如果补数不在哈希表中，说明还没有找到匹配的数对，将当前元素和其索引存入映射中，然后继续下一次循环。这种设计确保了在遍历过程中，哈希表中存储的都是已经访问过的元素，使得我们可以在 O(1) 时间内查找补数。

如果所有元素都遍历完毕但没有找到匹配，函数返回 null。这个算法的时间复杂度是 O(n)，因为只需要遍历数组一次，每次查找和插入操作都是 O(1)。空间复杂度是 O(n)，因为最坏情况下需要存储所有元素的映射关系。这种时间和空间的权衡使得算法在处理大数据量时更加高效。

3.5 查找过程详细展示

if (resultHashMap != null) {
    builder.appendLine("🔬 查找过程（哈希表法）")
    val map = mutableMapOf<Int, Int>()
    var found = false
    
    for (i in numbers.indices) {
        val current = numbers[i]
        val complement = targetValue - current
        val step = i + 1
        
        if (map.containsKey(complement)) {
            builder.appendLine("步骤 $step: 当前值=$current, 需要补数=$complement")
            builder.appendLine("  → 在哈希表中找到补数（索引 ${map[complement]}）")
            builder.appendLine("  → 找到匹配: [${map[complement]}, $i]")
            found = true
            break
        } else {
            builder.appendLine("步骤 $step: 当前值=$current, 需要补数=$complement")
            builder.appendLine("  → 补数不在哈希表中，将 $current 存入哈希表（索引 $i）")
            map[current] = i
        }
    }
}

代码解析：

这段代码实现了详细的查找过程输出，帮助用户理解哈希表算法是如何逐步查找匹配的数对的。首先检查是否找到了结果，只有在找到结果时才显示详细过程，避免不必要的输出。

然后创建一个可变映射 map 和标志变量 found，这些变量的作用与核心算法函数中的相同。使用单层循环遍历数组，在每一步中输出详细的操作信息。

对于每个元素，首先获取当前元素的值和需要的补数，计算步骤编号（从 1 开始，使用 i + 1）。然后检查补数是否在哈希表中。

如果找到补数，输出找到匹配的信息，包括当前值、需要的补数、补数在哈希表中的索引，以及最终找到的两个索引。然后设置 found 标志为 true，使用 break 跳出循环，因为已经找到了答案。

如果补数不在哈希表中，输出未找到的信息，包括当前值、需要的补数，以及将当前元素存入哈希表的操作。然后继续下一次循环。

这种逐步展示帮助用户理解哈希表算法的工作原理，特别是如何通过存储已访问的元素来快速查找补数，从而将时间复杂度从 O(n²) 降低到 O(n)。

3.6 所有可能组合的查找

builder.appendLine("📋 所有可能的组合")
val allPairs = mutableListOf<Pair<Int, Int>>()
for (i in numbers.indices) {
    for (j in i + 1 until numbers.size) {
        allPairs.add(Pair(i, j))
    }
}

val matchingPairs = allPairs.filter { numbers[it.first] + numbers[it.second] == targetValue }

if (matchingPairs.isNotEmpty()) {
    matchingPairs.forEachIndexed { idx, (i, j) ->
        builder.appendLine("组合 ${idx + 1}: 索引 [$i, $j] → 值 [${numbers[i]}, ${numbers[j]}] = ${numbers[i] + numbers[j]}")
    }
} else {
    builder.appendLine("无匹配组合")
}

代码解析：

这段代码实现了所有可能组合的查找和显示，帮助用户了解数组中所有满足条件的数对。首先创建一个可变列表 allPairs 用于存储所有可能的索引对。

然后使用双重循环生成所有可能的数对。外层循环遍历所有起始位置，内层循环遍历所有后续位置（从 i + 1 开始），确保每个数对只被生成一次。将每个索引对作为 Pair 添加到列表中。

接下来使用 filter 函数过滤出所有满足条件的数对。filter 是 Kotlin 集合的高阶函数，接受一个谓词函数，返回满足条件的所有元素。这里使用 { numbers[it.first] + numbers[it.second] == targetValue } 作为谓词，检查数对中两个元素的和是否等于目标值。

如果找到匹配的数对，使用 forEachIndexed 遍历并输出每个数对的详细信息，包括组合编号、两个索引、对应的值以及它们的和。使用解构声明 (i, j) 将 Pair 解构为两个变量，使代码更简洁。

如果没有找到匹配的数对，输出提示信息。这种详细的输出提供了全面的信息，帮助用户理解算法的查找结果和数组中所有可能满足条件的组合。