重构嵌套的 For 循环

Question

指示

给定一个整数数组，返回两个数字的索引，使它们相加到一个特定的目标。

您可能会假设每个输入都只有一个解决方案，并且您可能不会两次使用相同的元素。

例子

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

如何重构它以消除嵌套的 for 循环？我想降低时间复杂度。

代码

const twoSum = function(nums, target) {

    for(let i in nums){

      for(let j in nums) {

        if(nums[i] + nums[j] === target && nums[i] != nums[j]) {

            return [i, j];

        }

      }

    }

};

console.log(twoSum([2, 7, 11, 15], 9));

Answer 1

您可以将每个元素与目标的差异保存在对象中，结果作为键，索引作为值。这将在不循环整个内容的情况下检查对象内是否存在元素。在不同的循环中检查对象中是否存在数组元素，如果存在，则您已获得该对。附加条件是防止将元素与其自身进行比较。const twoSum = function(nums, target) {&nbsp;&nbsp;&nbsp; const temp = {};&nbsp; for(let i=0; i<nums.length; i++) {&nbsp; &nbsp; temp[target - nums[i]] = i;&nbsp; }&nbsp; for(let i=0; i<nums.length-1; i++) {&nbsp; &nbsp; if(temp[nums[i]] && temp[nums[i]] !== i) {&nbsp; &nbsp; &nbsp; return [i, temp[nums[i]]]&nbsp; &nbsp; }&nbsp; }};console.log(twoSum([2, 11, 7, 17], 9));console.log(twoSum([1, 3, 4, 2], 6));

Answer 2

由于这似乎是家庭作业，因此我将提出一些建议，但不会给出完整的解决方案：您当前的代码正在重复索引检查。例如，您正在循环索引 [0,1] 和 [1,0]，因为 a+b = b+a，它们的总和总是相同的。相反，我建议你的循环i从 0 到 len-1，你的循环j从 i+1 到 len-1。这样，您将永远不会重复检查。您当前检查的一部分包括条件nums[i] != nums[j]，但您的问题并未说明数组中的两个值不能相同。toSum([1, 4, 4], 8)是否可以使用4+4=8 之类的值调用此函数？如果是这样，那么您可以删除nums[i] != nums[j]检查以节省时间。目前尚不清楚提供的数组是否已排序。如果不是，那么您可以创建一个跟踪变量来说明您已经检查过的值，并防止在未来的迭代中检查它们。例如，如果您已经将值 4 与数组中的所有其他值进行了比较，但没有找到解决方案，那么如果您稍后在数组中遇到 4，则没有理由检查它。

Answer 3

你可以随着时间的推移解决这个问题O(n)。这种方法解决的条件是数组必须排序。let twosum = (arr, x) => {&nbsp; let s = 0,&nbsp; &nbsp; e = arr.length - 1;&nbsp; let loc = [];&nbsp; while (s < e) {&nbsp; &nbsp; if (arr[s] + arr[e] === x) {&nbsp; &nbsp; &nbsp; loc.push([s,e]);&nbsp; &nbsp; &nbsp; s++;&nbsp; &nbsp; &nbsp; e--;&nbsp; &nbsp; } else if (arr[s] + arr[e] < x) {&nbsp; &nbsp; &nbsp; s++;&nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; e--;&nbsp; &nbsp; }&nbsp; }&nbsp; return loc;};console.log(twosum([1, 2, 3, 4, 5, 7, 8], 9));console.log(twosum([2, 7, 11, 15], 9));如果有人感兴趣，这背后的算法：1.&nbsp; &nbsp;Set s value as 02.&nbsp; &nbsp;Set e value as last index say (arr.length - 1)3.&nbsp; &nbsp;While s is less than e i.e not pass one another4.&nbsp; &nbsp;Check if arr[s] + arr[e] === x then we find it.4.1. increment s value by 1 as there is no possibility to find any combination before the current s value4.2. decrement e value by 1 as there is no possibility to find any combination after the current e value4.3. collect the indexes where the match found.5.&nbsp; &nbsp;If arr[s] + arr[e] < x5.1&nbsp; increment s as there is no possibility to find any combination before the current s value. But there still has the possibility for the e value to get a match.6.&nbsp; &nbsp;If arr[s] + arr[e] > x6.1&nbsp; decrement e as there is no possibility to find any combination after the current e value. But there still has the possibility for the s value to get a match.