算法实践：二和

为什么要使用算法？

问题：两个和

我的初步解决方案

完善我的方法

编写替代解决方案

结论

为什么要使用算法？

根据定义，在软件开发中，算法是为完成特定任务而设计的计算机程序。每个算法都包含计算机为产生结果而采取的一系列步骤。使用算法的最终目标是以尽可能高效的方式找到结果或解决方案。

创建和研究算法是成为软件工程师的必备技能。当然，你可能不会遇到需要满足许多学习问题要求的情况，但你学习到的技巧在进行技术分析时将会大有裨益。你可能会发现，你研究的算法的某些部分能够提高应用程序的运行效率，或者返回最终用户所需的结果。

无论你如何使用算法，它都是一个很棒的问题解决工具。正因如此，我把练习算法开发作为个人目标。无论需要多长时间，我都会努力完成一系列编程挑战，每个挑战都旨在测试我对某些软件概念的掌握程度（或缺乏的知识）。我将利用这个博客来分享每个挑战中哪些做得好，哪些做得不好。如果你是一位软件开发者新手，或者正在探索成为一名开发者的可能性，我希望这些文章能够激励和鼓励你踏上个人的旅程！

问题：两个和

这项挑战的题目非常简单：编写一个函数，输入一个非空的整数数组和一个目标值，返回一个包含两个值的新数组，这两个值都来自输入数组，其和等于目标值。以下是我们希望函数执行的操作示例：

数组= [8, 1, 7, 5, -9, -11, 3]
目标值= 10

输出= [7, 3] 或 [3, 7]

如果数组中没有两个数字的和等于目标值，我们就返回一个空数组。还要注意的是，该函数不能将整数加到自身上（例如 5 + 5），并且应该假设最多只有一对数字的和等于目标值。

我的初步解决方案

虽然这个问题在我使用的平台上被归类为“简单”，但由于我几乎没有处理这类问题的经验，一开始确实觉得很有挑战性。大约30-35分钟后，我终于想出了一个通过所有测试的解决方案：

function twoSum(array, targetSum) {
    let finalArray = []
    let newArray = array

    for(i=0; i < array.length; i++){
        let targetValue = array[i]
        newArray.splice(i,1)

        newArray.map(value => {
            if (targetValue + value === targetSum){
                finalArray.push(targetValue)
                finalArray.push(value)
            }
        })

        if (finalArray.length === 0){
            newArray.splice(i, 0, targetValue)
        } else {
            return finalArray;
        }
    }
    return finalArray
}

分解代码，我首先定义了两个数组，一个设置为空数组，另一个设置为传递给函数的数组。然后，我启动一个 for 循环，循环遍历数组的长度。在 for 循环中，我定义了另一个变量，该变量等于数组中的某个值，其中i是索引号。每次循环递增时，此变量的值都会发生变化。然后，我取出 newArray 并拼接出i的索引值。

移除此值后，我通过 newArray 进行映射，检查与 targetValue 一起添加的其他值是否等于 targetSum。如果这两个值返回正确的和，我将每个值推送到 finalArray 中。

映射完成后，我会运行另一个条件语句来检查 finalArray 的长度。如果长度等于零，则将目标值重新插入到 newArray 中索引为i的位置，继续循环。如果长度大于零，则表示存在值，程序将返回 finalArray。此条件语句之后的最后一行返回代码用于在循环执行完毕后仍未找到整数对时返回空数组。

完善我的方法

虽然这个算法确实通过了题目中的挑战，但它在多个层面上都很糟糕。事实上，我太高兴了，以至于直接通过了测试，提交了这个问题，而没有花时间重构我的工作。几天后，我终于决定看一看，天哪，它真是太难了！

首先，我定义了几个冗余变量，最明显的例子就是一开始就定义的 newArray 变量。大量的变量让代码变得杂乱无章，阅读代码的人越来越难以理解这个函数的实际功能。为了便于重构，我知道我需要删除这些冗余变量。

我本来想用 for 循环，但不知怎么的，我却做了个令人费解的决定，要用 map。当然，map 可以用来迭代数组并检查每个值，但它的目的是返回一个新数组。我应该用第二个 for 循环来代替 map，这样就能达到同样的迭代目的，而且不需要返回值。

最后，我把返回最终数组的任务弄得比实际需要的更难。与其创建一个空数组，将正确的值存入该数组，然后检查数组中是否有值，不如直接返回一个包含所有值的数组：

return [value1, value2]

我必须以不同的方式设置我的代码，但这绝对是做事的首选方式。

编写替代解决方案

在审查了这些问题、研究了大 O 符号并听取了其他开发人员的建议后，我提交了第二个解决方案：

function twoSum(array, targetSum) {
   array.sort((a,b) => a - b);
   let leftIndex = 0
   let rightIndex = array.length-1

   while(leftIndex < rightIndex){
    const currentSum = array[leftIndex] + array[rightIndex]

    if(currentSum === targetSum){
       return [array[leftIndex], array[rightIndex]]
    } else if (currentSum < targetSum){
            leftIndex++
    } else if (currentSum > targetSum){
            rightIndex--
    }
   }
   return [];
}

在这个版本中，我首先将数组中的整数按从小到大的顺序排序。然后，我创建了两个变量来表示数组的第一个和最后一个索引。接着，我启动了一个 while 循环，该循环持续运行，直到 leftIndex 大于或等于 rightIndex，或者执行了 return 语句。

在循环中，我创建了另一个变量 currentSum，用于保存左索引值和右索引值的和。基于此变量，我创建了一个条件语句，用于检查该值是否等于 targetSum。如果相等，函数将返回一个包含两个索引值的数组。其他语句检查 currentSum 是大于还是小于 targetSum，并调整任一索引值以改变 currentSum。如果数组中的每个值都已求值，且没有任何一对索引值与 targetSum 相等，则算法将返回一个空数组。

这种方法之所以有效，得益于数字排序以及左右“指针”的使用。让我们使用之前定义的数组，并将其传递给这个算法。以下是进入循环前的初始值：

目标值= 10
排序数组= [-11, -9, 1, 3, 5, 7, 8]
leftIndex = 0
rightIndex = 6

进入循环后，我们将 -11 和 8 相加，结果为 -3。由于 -3 小于 10，因此第一个else if语句会被执行，leftIndex 值会加 1，也就是 -9 在数组中的索引。随着时间的推移，函数会相应地调整每个索引的位置，直到一对元素的和等于 targetSum。在上例中，当 leftIndex 等于 3 且 rightIndex 等于 5 时，就会发生这种情况。

结论

即使是面对一些比较简单的问题，回到过去并弄清楚算法是如何运作的以及为什么运作的，感觉真是太棒了。能够从错误中吸取教训，让代码运行得更高效，这能增强你的信心，让你更有信心去应对下一个编程挑战。希望未来回首往事时，我能意识到这些小小的成就是知识的基石，帮助我成为一名更全面的开发人员！