KMP OpenHarmony 两数之和(Two Sum)算法对比
两数之和问题（Two Sum）是LeetCode经典题目，在金融、电商等领域有广泛应用。本文探讨了五种解决方案：1）暴力破解法（O(n²)时间）；2）哈希表法（最优O(n)时间）；3）排序+双指针法（O(n log n)时间）；4）优化哈希表法；5）集合法（仅判断存在性）。Kotlin实现展示了每种方法的代码，并提供了算法选择指南：小数据用暴力法，大数据推荐哈希表法，需要排序结果用双指针法。文章还
·
欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.csdn.net
文章概述
两数之和（Two Sum）是LeetCode上最受欢迎的问题之一，也是许多技术面试的必考题目。这个问题看似简单，但实际上涉及多种不同的解决方案，从暴力破解到哈希表优化，再到双指针技巧，每种方法都展现了不同的算法设计思想。两数之和问题不仅在学术研究中有重要意义，而且在实际应用中也广泛存在。
在金融系统、数据分析、推荐系统等领域，两数之和问题都有其身影。例如，在电商平台中，我们可能需要找到两个商品，使得它们的价格之和等于用户的预算。在金融交易中，我们需要找到两笔交易，使得它们的金额之和等于某个特定值。在数据分析中，我们需要找到数据集中的两个数据点，使得它们的和满足特定条件。
本文将深入探讨如何在KMP（Kotlin Multiplatform）框架下实现两数之和问题的多种解决方案，并展示如何在OpenHarmony鸿蒙平台上进行跨端调用。我们将对比不同算法的时间复杂度、空间复杂度和实际性能，帮助开发者选择最合适的方案。
算法原理详解
问题定义
给定一个整数数组和一个整数目标值，找出数组中两个不同位置的数，使得它们的和等于目标值。返回这两个数的下标。每个输入只有一个答案，且同一个元素不能使用两次。
例如：
- 输入：
nums = [2, 7, 11, 15],target = 9 - 输出：
[0, 1] - 解释：因为
nums[0] + nums[1] == 9，返回[0, 1]
另一个例子：
- 输入：
nums = [3, 2, 4],target = 6 - 输出：
[1, 2] - 解释：因为
nums[1] + nums[2] == 6，返回[1, 2]
解决方案对比
方案1：暴力破解法（Brute Force）
最直观的方法是使用两层嵌套循环，对数组中的每一对元素进行检查。这种方法的优点是实现简单，易于理解；缺点是时间复杂度为O(n²)，当数组规模较大时性能会显著下降。
时间复杂度：O(n²)
空间复杂度：O(1)
优点：实现简单，易于理解
缺点：性能较差，不适合大规模数据
适用场景：数组规模较小（n < 1000）
方案2：哈希表法（Hash Map）
这是解决两数之和问题的最优方案。我们使用一个哈希表来存储已经遍历过的元素及其下标。对于每个元素，我们检查target - nums[i]是否在哈希表中。如果存在，我们就找到了答案；如果不存在，我们将当前元素添加到哈希表中。
时间复杂度：O(n)
空间复杂度：O(n)
优点：时间复杂度最优，适合大规模数据
缺点：需要额外的O(n)空间
适用场景：数组规模较大（n > 1000），需要高效查询
方案3：排序+双指针法（Sort + Two Pointers）
先对数组进行排序，然后使用两个指针分别指向数组的开始和结束。根据两个指针指向的元素之和与目标值的大小关系，移动指针。这种方法的优点是空间复杂度较低（如果不考虑排序空间），缺点是会改变原数组的顺序，需要额外处理下标映射。
时间复杂度：O(n log n)
空间复杂度：O(1)或O(n)（取决于排序算法）
优点：空间复杂度相对较低
缺点：需要额外的下标映射逻辑
适用场景：需要找到所有满足条件的数对，而不仅仅是一对
方案4：哈希表+优化查询（Optimized Hash Map）
在基础哈希表法的基础上，进行各种优化，例如使用更高效的哈希函数、减少哈希碰撞等。这种方法的优点是在实际应用中性能更好。
时间复杂度：O(n)
空间复杂度：O(n)
优点：实际性能更好，代码更优雅
缺点：实现相对复杂
适用场景：性能要求较高的场景
方案5：集合法（Set-based Approach）
使用集合（Set）而不是哈希表来存储元素。这种方法的优点是代码更加简洁，缺点是无法直接获取下标。
时间复杂度：O(n)
空间复杂度：O(n)
优点：代码简洁，易于理解
缺点：无法直接获取下标
适用场景：只需要判断是否存在满足条件的数对
算法选择指南
- 数组规模小且性能要求不高：使用暴力破解法
- 需要高效查询且内存充足：使用哈希表法（推荐）
- 需要找到所有数对或需要排序结果：使用双指针法
- 内存受限：使用双指针法
- 只需要判断是否存在：使用集合法
Kotlin实现
完整的Kotlin代码实现
/**
* 两数之和(Two Sum)算法工具类 - KMP OpenHarmony
* 提供多种解决方案来找到数组中两个数，使其和等于目标值
*/
object TwoSumUtils {
/**
* 方案1：暴力破解法
* 时间复杂度：O(n²)
* 空间复杂度：O(1)
*
* 原理：
* 使用两层嵌套循环遍历数组中的每一对元素
* 检查它们的和是否等于目标值
*/
fun twoSumBruteForce(nums: IntArray, target: Int): IntArray {
for (i in nums.indices) {
for (j in i + 1 until nums.size) {
if (nums[i] + nums[j] == target) {
return intArrayOf(i, j)
}
}
}
return intArrayOf(-1, -1)
}
/**
* 方案2：哈希表法（推荐）
* 时间复杂度：O(n)
* 空间复杂度：O(n)
*
* 原理：
* 使用HashMap存储已遍历的元素及其下标
* 对于每个元素，检查 target - nums[i] 是否在Map中
*/
fun twoSumHashMap(nums: IntArray, target: Int): IntArray {
val map = mutableMapOf<Int, Int>()
for (i in nums.indices) {
val complement = target - nums[i]
if (map.containsKey(complement)) {
return intArrayOf(map[complement]!!, i)
}
map[nums[i]] = i
}
return intArrayOf(-1, -1)
}
/**
* 方案3：排序+双指针法
* 时间复杂度：O(n log n)
* 空间复杂度：O(n)
*/
fun twoSumTwoPointers(nums: IntArray, target: Int): IntArray {
val indexed = nums.mapIndexed { index, value -> Pair(value, index) }
val sorted = indexed.sortedBy { it.first }
var left = 0
var right = sorted.size - 1
while (left < right) {
val sum = sorted[left].first + sorted[right].first
when {
sum == target -> {
return intArrayOf(sorted[left].second, sorted[right].second)
}
sum < target -> left++
else -> right--
}
}
return intArrayOf(-1, -1)
}
/**
* 方案4：哈希表+优化查询
* 时间复杂度：O(n)
* 空间复杂度：O(n)
*/
fun twoSumOptimized(nums: IntArray, target: Int): IntArray {
val seen = mutableMapOf<Int, Int>()
for (i in nums.indices) {
val complement = target - nums[i]
// 检查是否已经看过这个补数
if (complement in seen) {
return intArrayOf(seen[complement]!!, i)
}
// 只有在没有找到答案时才添加到map
if (nums[i] !in seen) {
seen[nums[i]] = i
}
}
return intArrayOf(-1, -1)
}
/**
* 方案5：集合法
* 时间复杂度：O(n)
* 空间复杂度：O(n)
*/
fun twoSumExists(nums: IntArray, target: Int): Boolean {
val seen = mutableSetOf<Int>()
for (num in nums) {
val complement = target - num
if (complement in seen) {
return true
}
seen.add(num)
}
return false
}
/**
* 找到所有满足条件的数对
* 时间复杂度：O(n)
* 空间复杂度：O(n)
*/
fun twoSumAll(nums: IntArray, target: Int): List<Pair<Int, Int>> {
val result = mutableListOf<Pair<Int, Int>>()
val seen = mutableSetOf<Int>()
for (num in nums) {
val complement = target - num
if (complement in seen) {
result.add(Pair(complement, num))
}
seen.add(num)
}
return result
}
/**
* 性能演示函数 - 对比多种方法的性能
*/
fun performanceDemo(size: Int = 10000): String {
val result = StringBuilder()
result.append("两数之和性能对比 (数组大小: $size)\n")
result.append("=".repeat(70)).append("\n\n")
// 生成测试数据
val nums = IntArray(size) { (Math.random() * 10000).toInt() }
val target = nums[0] + nums[1]
// 方案1：暴力破解法（仅对小数据集）
if (size <= 1000) {
val time1 = measureTimeMillis {
twoSumBruteForce(nums, target)
}
result.append("方案1 - 暴力破解法\n")
result.append("耗时: ${time1}ms\n")
result.append("时间复杂度: O(n²)\n\n")
} else {
result.append("方案1 - 暴力破解法\n")
result.append("耗时: 跳过（数据太大）\n\n")
}
// 方案2：哈希表法
val time2 = measureTimeMillis {
twoSumHashMap(nums, target)
}
result.append("方案2 - 哈希表法（推荐）\n")
result.append("耗时: ${time2}ms\n")
result.append("时间复杂度: O(n)\n\n")
// 方案3：双指针法
val time3 = measureTimeMillis {
twoSumTwoPointers(nums, target)
}
result.append("方案3 - 排序+双指针法\n")
result.append("耗时: ${time3}ms\n")
result.append("时间复杂度: O(n log n)\n\n")
// 方案4：优化哈希表
val time4 = measureTimeMillis {
twoSumOptimized(nums, target)
}
result.append("方案4 - 哈希表+优化查询\n")
result.append("耗时: ${time4}ms\n")
result.append("时间复杂度: O(n)\n\n")
// 方案5：集合法
val time5 = measureTimeMillis {
twoSumExists(nums, target)
}
result.append("方案5 - 集合法\n")
result.append("耗时: ${time5}ms\n")
result.append("时间复杂度: O(n)\n\n")
// 性能对比
result.append("性能对比总结\n")
result.append("-".repeat(70)).append("\n")
result.append("最快方案: 哈希表法\n")
result.append("推荐方案: 哈希表法（综合考虑时间和空间）\n")
return result.toString()
}
}
// 扩展函数
fun IntArray.twoSum(target: Int): IntArray {
return TwoSumUtils.twoSumHashMap(this, target)
}
// 使用示例
fun main() {
println("KMP OpenHarmony 两数之和(Two Sum)算法演示\n")
val nums = intArrayOf(2, 7, 11, 15)
val target = 9
println("输入数组: ${nums.joinToString(", ")}")
println("目标值: $target\n")
// 方案1
val result1 = TwoSumUtils.twoSumBruteForce(nums, target)
println("方案1 - 暴力破解法: [${result1[0]}, ${result1[1]}]")
// 方案2
val result2 = TwoSumUtils.twoSumHashMap(nums, target)
println("方案2 - 哈希表法: [${result2[0]}, ${result2[1]}]")
// 方案3
val result3 = TwoSumUtils.twoSumTwoPointers(nums, target)
println("方案3 - 双指针法: [${result3[0]}, ${result3[1]}]")
// 方案4
val result4 = TwoSumUtils.twoSumOptimized(nums, target)
println("方案4 - 优化哈希表: [${result4[0]}, ${result4[1]}]")
// 方案5
val result5 = TwoSumUtils.twoSumExists(nums, target)
println("方案5 - 集合法: $result5")
println("\n性能演示:")
println(TwoSumUtils.performanceDemo(10000))
}
fun measureTimeMillis(block: () -> Unit): Long {
val start = System.currentTimeMillis()
block()
return System.currentTimeMillis() - start
}
Kotlin实现的详细说明
Kotlin实现提供了五种不同的两数之和解决方案。暴力破解法虽然时间复杂度较高，但在数组规模较小时仍然是可行的，并且代码最为简洁。哈希表法是最优方案，通过一次遍历就能找到答案，时间复杂度为O(n)，这是理论上的最优复杂度。
双指针法虽然需要排序，但在需要找到所有满足条件的数对时非常有用。优化的哈希表法在基础哈希表法的基础上进行了优化，只在必要时添加元素到map中，从而减少了内存占用。集合法虽然无法直接获取下标，但在只需要判断是否存在满足条件的数对时非常有用。
JavaScript实现
完整的JavaScript代码实现
/**
* 两数之和(Two Sum)算法工具类 - JavaScript版本
* 用于在Web和Node.js环境中使用
*/
class TwoSumJS {
/**
* 方案1：暴力破解法
* @param {number[]} nums - 输入数组
* @param {number} target - 目标值
* @returns {number[]} 返回两个数的下标
*/
static twoSumBruteForce(nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return [-1, -1];
}
/**
* 方案2：哈希表法（推荐）
* @param {number[]} nums - 输入数组
* @param {number} target - 目标值
* @returns {number[]} 返回两个数的下标
*/
static twoSumHashMap(nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (map.has(complement)) {
return [map.get(complement), i];
}
map.set(nums[i], i);
}
return [-1, -1];
}
/**
* 方案3：排序+双指针法
* @param {number[]} nums - 输入数组
* @param {number} target - 目标值
* @returns {number[]} 返回两个数的下标
*/
static twoSumTwoPointers(nums, target) {
const indexed = nums.map((value, index) => [value, index]);
indexed.sort((a, b) => a[0] - b[0]);
let left = 0;
let right = indexed.length - 1;
while (left < right) {
const sum = indexed[left][0] + indexed[right][0];
if (sum === target) {
return [indexed[left][1], indexed[right][1]];
} else if (sum < target) {
left++;
} else {
right--;
}
}
return [-1, -1];
}
/**
* 方案4：哈希表+优化查询
* @param {number[]} nums - 输入数组
* @param {number} target - 目标值
* @returns {number[]} 返回两个数的下标
*/
static twoSumOptimized(nums, target) {
const seen = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (seen.has(complement)) {
return [seen.get(complement), i];
}
if (!seen.has(nums[i])) {
seen.set(nums[i], i);
}
}
return [-1, -1];
}
/**
* 方案5：集合法
* @param {number[]} nums - 输入数组
* @param {number} target - 目标值
* @returns {boolean} 是否存在满足条件的数对
*/
static twoSumExists(nums, target) {
const seen = new Set();
for (const num of nums) {
const complement = target - num;
if (seen.has(complement)) {
return true;
}
seen.add(num);
}
return false;
}
/**
* 找到所有满足条件的数对
* @param {number[]} nums - 输入数组
* @param {number} target - 目标值
* @returns {number[][]} 返回所有满足条件的数对
*/
static twoSumAll(nums, target) {
const result = [];
const seen = new Set();
for (const num of nums) {
const complement = target - num;
if (seen.has(complement)) {
result.push([complement, num]);
}
seen.add(num);
}
return result;
}
/**
* 性能演示函数
* @param {number} size - 数组大小
* @returns {string} 性能报告
*/
static performanceDemo(size = 10000) {
let result = `两数之和性能对比 (数组大小: ${size})\n`;
result += '='.repeat(70) + '\n\n';
// 生成测试数据
const nums = Array.from({ length: size }, () => Math.floor(Math.random() * 10000));
const target = nums[0] + nums[1];
// 方案1
if (size <= 1000) {
const start1 = performance.now();
TwoSumJS.twoSumBruteForce(nums, target);
const time1 = performance.now() - start1;
result += `方案1 - 暴力破解法: ${time1.toFixed(2)}ms\n`;
result += '时间复杂度: O(n²)\n\n';
} else {
result += `方案1 - 暴力破解法: 跳过（数据太大）\n\n`;
}
// 方案2
const start2 = performance.now();
TwoSumJS.twoSumHashMap(nums, target);
const time2 = performance.now() - start2;
result += `方案2 - 哈希表法（推荐）: ${time2.toFixed(2)}ms\n`;
result += '时间复杂度: O(n)\n\n';
// 方案3
const start3 = performance.now();
TwoSumJS.twoSumTwoPointers(nums, target);
const time3 = performance.now() - start3;
result += `方案3 - 排序+双指针法: ${time3.toFixed(2)}ms\n`;
result += '时间复杂度: O(n log n)\n\n';
// 方案4
const start4 = performance.now();
TwoSumJS.twoSumOptimized(nums, target);
const time4 = performance.now() - start4;
result += `方案4 - 哈希表+优化查询: ${time4.toFixed(2)}ms\n`;
result += '时间复杂度: O(n)\n\n';
// 方案5
const start5 = performance.now();
TwoSumJS.twoSumExists(nums, target);
const time5 = performance.now() - start5;
result += `方案5 - 集合法: ${time5.toFixed(2)}ms\n`;
result += '时间复杂度: O(n)\n\n';
result += '性能对比总结\n';
result += '-'.repeat(70) + '\n';
result += '最快方案: 哈希表法\n';
result += '推荐方案: 哈希表法（综合考虑时间和空间）\n';
return result;
}
}
// 导出供Node.js使用
if (typeof module !== 'undefined' && module.exports) {
module.exports = TwoSumJS;
}
JavaScript实现的详细说明
JavaScript版本的实现与Kotlin版本在逻辑上完全一致，但充分利用了JavaScript的语言特性。在哈希表实现中，我们使用了原生的Map对象，它提供了O(1)的查询性能。在双指针实现中，我们使用了map和sort方法，这些都是JavaScript数组的高效操作。
JavaScript的performance.now()方法提供了微秒级的精度，使得性能测试更加准确。在实际应用中，开发者可以使用这个性能演示函数来选择最适合的算法。值得注意的是，JavaScript中的Map对象比普通对象更适合用作哈希表，因为它提供了更好的性能和更清晰的API。
ArkTS调用实现
完整的ArkTS代码实现
/**
* 两数之和(Two Sum)工具 - ArkTS版本（OpenHarmony鸿蒙）
* 用于在鸿蒙应用中实现两数之和算法
*/
import { webview } from '@kit.ArkWeb';
import { common } from '@kit.AbilityKit';
@Entry
@Component
struct TwoSumPage {
@State inputArray: string = '2,7,11,15';
@State targetValue: number = 9;
@State result: string = '';
@State selectedMethod: string = '哈希表法';
@State isLoading: boolean = false;
@State allResults: string = '';
@State performanceData: string = '';
@State showPerformance: boolean = false;
// Web视图控制器
webviewController: webview.WebviewController = new webview.WebviewController();
/**
* 解析输入数组
*/
parseArray(input: string): number[] {
return input.split(',').map(str => parseInt(str.trim())).filter(num => !isNaN(num));
}
/**
* 方案1：暴力破解法
*/
twoSumBruteForce(nums: number[], target: number): number[] {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return [-1, -1];
}
/**
* 方案2：哈希表法（推荐）
*/
twoSumHashMap(nums: number[], target: number): number[] {
const map = new Map<number, number>();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (map.has(complement)) {
return [map.get(complement)!, i];
}
map.set(nums[i], i);
}
return [-1, -1];
}
/**
* 方案3：排序+双指针法
*/
twoSumTwoPointers(nums: number[], target: number): number[] {
const indexed = nums.map((value, index) => [value, index]);
indexed.sort((a, b) => a[0] - b[0]);
let left = 0;
let right = indexed.length - 1;
while (left < right) {
const sum = indexed[left][0] + indexed[right][0];
if (sum === target) {
return [indexed[left][1], indexed[right][1]];
} else if (sum < target) {
left++;
} else {
right--;
}
}
return [-1, -1];
}
/**
* 方案4：哈希表+优化查询
*/
twoSumOptimized(nums: number[], target: number): number[] {
const seen = new Map<number, number>();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (seen.has(complement)) {
return [seen.get(complement)!, i];
}
if (!seen.has(nums[i])) {
seen.set(nums[i], i);
}
}
return [-1, -1];
}
/**
* 方案5：集合法
*/
twoSumExists(nums: number[], target: number): boolean {
const seen = new Set<number>();
for (const num of nums) {
const complement = target - num;
if (seen.has(complement)) {
return true;
}
seen.add(num);
}
return false;
}
/**
* 找到所有满足条件的数对
*/
twoSumAll(nums: number[], target: number): number[][] {
const result: number[][] = [];
const seen = new Set<number>();
for (const num of nums) {
const complement = target - num;
if (seen.has(complement)) {
result.push([complement, num]);
}
seen.add(num);
}
return result;
}
/**
* 执行两数之和计算
*/
async executeTwoSum() {
this.isLoading = true;
this.showPerformance = false;
try {
const nums = this.parseArray(this.inputArray);
if (nums.length < 2) {
this.result = '错误：数组至少需要2个元素';
this.isLoading = false;
return;
}
let resultArray: number[] = [];
switch (this.selectedMethod) {
case '暴力破解法':
resultArray = this.twoSumBruteForce(nums, this.targetValue);
break;
case '哈希表法':
resultArray = this.twoSumHashMap(nums, this.targetValue);
break;
case '双指针法':
resultArray = this.twoSumTwoPointers(nums, this.targetValue);
break;
case '优化哈希表':
resultArray = this.twoSumOptimized(nums, this.targetValue);
break;
}
if (resultArray[0] === -1) {
this.result = '未找到满足条件的两个数';
} else {
const num1 = nums[resultArray[0]];
const num2 = nums[resultArray[1]];
this.result = `找到！下标: [${resultArray[0]}, ${resultArray[1]}]\n` +
`数值: [${num1}, ${num2}]\n` +
`验证: ${num1} + ${num2} = ${num1 + num2}`;
}
// 同时获取所有数对
const allPairs = this.twoSumAll(nums, this.targetValue);
if (allPairs.length > 0) {
this.allResults = `所有满足条件的数对：\n${allPairs.map(pair => `[${pair[0]}, ${pair[1]}]`).join('\n')}`;
} else {
this.allResults = '没有找到满足条件的数对';
}
} catch (error) {
this.result = '计算错误：' + error;
}
this.isLoading = false;
}
/**
* 执行性能演示
*/
async executePerformanceDemo() {
this.isLoading = true;
this.showPerformance = true;
try {
const size = 10000;
const nums = Array.from({ length: size }, () => Math.floor(Math.random() * 10000));
const target = nums[0] + nums[1];
let result = `两数之和性能对比 (数组大小: ${size})\n`;
result += '='.repeat(70) + '\n\n';
// 方案2
const start2 = Date.now();
this.twoSumHashMap(nums, target);
const time2 = Date.now() - start2;
result += `方案2 - 哈希表法: ${time2}ms\n`;
result += '时间复杂度: O(n)\n\n';
// 方案3
const start3 = Date.now();
this.twoSumTwoPointers(nums, target);
const time3 = Date.now() - start3;
result += `方案3 - 双指针法: ${time3}ms\n`;
result += '时间复杂度: O(n log n)\n\n';
// 方案4
const start4 = Date.now();
this.twoSumOptimized(nums, target);
const time4 = Date.now() - start4;
result += `方案4 - 优化哈希表: ${time4}ms\n`;
result += '时间复杂度: O(n)\n\n';
// 方案5
const start5 = Date.now();
this.twoSumExists(nums, target);
const time5 = Date.now() - start5;
result += `方案5 - 集合法: ${time5}ms\n`;
result += '时间复杂度: O(n)\n\n';
result += '性能对比总结\n';
result += '-'.repeat(70) + '\n';
result += '最快方案: 哈希表法\n';
result += '推荐方案: 哈希表法（综合考虑时间和空间）\n';
this.performanceData = result;
} catch (error) {
this.performanceData = '演示失败：' + error;
}
this.isLoading = false;
}
build() {
Column() {
// 顶部栏
Row() {
Text('两数之和(Two Sum)')
.fontSize(24)
.fontWeight(FontWeight.Bold)
.fontColor(Color.White)
}
.width('100%')
.height(60)
.backgroundColor('#1565C0')
.justifyContent(FlexAlign.Center)
// 主内容
Scroll() {
Column({ space: 16 }) {
// 输入数组
Column() {
Text('输入数组:')
.fontSize(14)
.fontWeight(FontWeight.Bold)
.width('100%')
TextInput({ placeholder: '请输入数组，用逗号分隔' })
.value(this.inputArray)
.onChange((value: string) => {
this.inputArray = value;
})
.width('100%')
.padding(8)
.backgroundColor(Color.White)
.borderRadius(4)
}
.width('100%')
.padding(12)
.backgroundColor('#E3F2FD')
.borderRadius(8)
// 目标值
Column() {
Text('目标值:')
.fontSize(14)
.fontWeight(FontWeight.Bold)
.width('100%')
Row() {
TextInput({ placeholder: '请输入目标值' })
.value(this.targetValue.toString())
.onChange((value: string) => {
const num = parseInt(value);
if (!isNaN(num)) {
this.targetValue = num;
}
})
.width('70%')
.padding(8)
.backgroundColor(Color.White)
.borderRadius(4)
Text(this.targetValue.toString())
.fontSize(14)
.fontWeight(FontWeight.Bold)
.width('25%')
.textAlign(TextAlign.Center)
}
.width('100%')
.justifyContent(FlexAlign.SpaceBetween)
}
.width('100%')
.padding(12)
.backgroundColor('#E3F2FD')
.borderRadius(8)
// 方法选择
Column() {
Text('选择算法:')
.fontSize(14)
.fontWeight(FontWeight.Bold)
.width('100%')
Select([
{ value: '暴力破解法' },
{ value: '哈希表法' },
{ value: '双指针法' },
{ value: '优化哈希表' }
])
.value(this.selectedMethod)
.onSelect((index: number, value: string) => {
this.selectedMethod = value;
})
.width('100%')
}
.width('100%')
.padding(12)
.backgroundColor('#E3F2FD')
.borderRadius(8)
// 结果显示
if (this.result) {
Column() {
Text('计算结果:')
.fontSize(14)
.fontWeight(FontWeight.Bold)
.width('100%')
Text(this.result)
.fontSize(12)
.width('100%')
.padding(8)
.backgroundColor('#F5F5F5')
.borderRadius(4)
}
.width('100%')
.padding(12)
.backgroundColor('#F5F5F5')
.borderRadius(8)
}
// 所有数对显示
if (this.allResults) {
Column() {
Text('所有数对:')
.fontSize(14)
.fontWeight(FontWeight.Bold)
.width('100%')
Text(this.allResults)
.fontSize(12)
.width('100%')
.padding(8)
.backgroundColor('#E8F5E9')
.borderRadius(4)
}
.width('100%')
.padding(12)
.backgroundColor('#E8F5E9')
.borderRadius(8)
}
// 性能数据显示
if (this.showPerformance && this.performanceData) {
Column() {
Text('性能对比:')
.fontSize(14)
.fontWeight(FontWeight.Bold)
.width('100%')
Text(this.performanceData)
.fontSize(12)
.fontFamily('monospace')
.width('100%')
.padding(8)
.backgroundColor('#FFF3E0')
.borderRadius(4)
}
.width('100%')
.padding(12)
.backgroundColor('#FFF3E0')
.borderRadius(8)
}
// 按钮组
Row({ space: 12 }) {
Button('执行计算')
.width('48%')
.onClick(() => this.executeTwoSum())
.enabled(!this.isLoading)
Button('性能演示')
.width('48%')
.onClick(() => this.executePerformanceDemo())
.enabled(!this.isLoading)
}
.width('100%')
// 加载指示器
if (this.isLoading) {
LoadingProgress()
.width(40)
.height(40)
}
}
.width('100%')
.padding(16)
}
.layoutWeight(1)
}
.width('100%')
.height('100%')
.backgroundColor('#FAFAFA')
}
}
ArkTS实现的详细说明
ArkTS版本为OpenHarmony鸿蒙平台提供了完整的用户界面。通过@State装饰器，我们可以管理应用的状态，当用户输入改变时，UI会自动更新。这个实现包含了输入数组、目标值的输入框，以及算法选择的下拉菜单。
在计算结果的显示中，我们不仅显示了找到的两个数的下标，还显示了它们的实际值和验证信息。这样用户可以直观地看到算法的正确性。同时，我们还提供了"所有数对"的显示，这对于需要找到所有满足条件的数对的场景非常有用。
性能演示功能允许用户在应用中直接看到不同算法的性能差异。通过对比10000个元素的数组，用户可以清楚地看到为什么哈希表法是推荐方案。
应用场景分析
1. 电商推荐系统
在电商平台中，两数之和问题可以用于推荐商品组合。例如，用户有一定的预算，系统需要找到两个商品，使得它们的价格之和等于用户的预算。这样可以帮助用户快速找到最合适的商品组合。
2. 金融交易系统
在金融系统中，两数之和问题可以用于检测异常交易。例如，系统需要找到两笔交易，使得它们的金额之和等于某个特定值，这可能表示存在欺诈行为或需要特殊处理的交易。
3. 数据分析
在数据分析中，两数之和问题可以用于找到数据集中的特定模式。例如，在时间序列数据中，我们需要找到两个时间点，使得它们的值之和等于某个阈值，这可能表示某种重要的事件或趋势。
4. 游戏开发
在游戏开发中，两数之和问题可以用于游戏逻辑。例如，在卡牌游戏中，玩家需要选择两张卡牌，使得它们的数值之和等于目标值，才能完成任务。
5. 密码学和安全
在密码学应用中，两数之和问题可以用于生成或验证特定的密钥模式。例如，系统可能需要找到两个数，使得它们的和等于某个特定的哈希值。
性能优化建议
1. 选择合适的算法
对于大多数实际应用，哈希表法是最优选择。它提供了O(n)的时间复杂度，这是理论上的最优复杂度。只有在内存极其受限的情况下，才应该考虑使用双指针法。
2. 数据预处理
在处理大规模数据时，可以先进行数据验证和清洗，移除无效数据。这可以减少实际需要处理的数据量，从而提高性能。
3. 缓存优化
在需要多次查询的场景中，可以预先构建哈希表，然后进行多次查询。这样可以避免重复的哈希表构建过程。
4. 并行处理
对于非常大的数据集，可以考虑将数据分片，在多个线程或进程中并行处理。但需要注意的是，并行处理的开销可能会抵消性能收益，需要根据实际情况进行评估。
总结
两数之和是一个经典的算法问题，虽然问题陈述简单，但其解决方案涉及多种不同的技术和思想。通过在KMP框架下实现这个算法，我们可以在多个平台上使用同一套代码，提高开发效率。
哈希表法是解决这个问题的最优方案，提供了O(n)的时间复杂度。在OpenHarmony鸿蒙平台上，我们可以通过ArkTS调用Kotlin编译的JavaScript代码，或者直接在ArkTS中实现算法，实现真正的跨平台开发。
掌握这个经典问题的多种解决方案，不仅能够帮助开发者在面试中获得好成绩，更重要的是能够培养解决问题的思维方式。在实际项目中，灵活应用这些算法和优化技巧，可以显著提升应用的性能和用户体验。
开源鸿蒙跨平台开发社区汇聚开发者与厂商，共建“一次开发，多端部署”的开源生态，致力于降低跨端开发门槛，推动万物智联创新。
更多推荐
19
0- 0
已为社区贡献14条内容
所有评论(0)