首頁猿問重構(gòu)嵌套的 For 循環(huán)

重構(gòu)嵌套的 For 循環(huán)

JavaScript

繁星點(diǎn)點(diǎn)滴滴 2022-05-26 10:22:06

指示給定一個(gè)整數(shù)數(shù)組，返回兩個(gè)數(shù)字的索引，使它們相加到一個(gè)特定的目標(biāo)。您可能會(huì)假設(shè)每個(gè)輸入都只有一個(gè)解決方案，并且您可能不會(huì)兩次使用相同的元素。例子Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].如何重構(gòu)它以消除嵌套的 for 循環(huán)？我想降低時(shí)間復(fù)雜度。代碼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));

查看完整描述

3 回答

明月笑刀無情

TA貢獻(xiàn)1828條經(jīng)驗(yàn) 獲得超4個(gè)贊

您可以將每個(gè)元素與目標(biāo)的差異保存在對(duì)象中，結(jié)果作為鍵，索引作為值。這將在不循環(huán)整個(gè)內(nèi)容的情況下檢查對(duì)象內(nèi)是否存在元素。在不同的循環(huán)中檢查對(duì)象中是否存在數(shù)組元素，如果存在，則您已獲得該對(duì)。附加條件是防止將元素與其自身進(jìn)行比較。

const twoSum = function(nums, target) {

const temp = {};

for(let i=0; i<nums.length; i++) {

temp[target - nums[i]] = i;

}

for(let i=0; i<nums.length-1; i++) {

if(temp[nums[i]] && temp[nums[i]] !== i) {

return [i, temp[nums[i]]]

}

};

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

console.log(twoSum([1, 3, 4, 2], 6));

反對(duì) 回復(fù) 2022-05-26

九州編程

TA貢獻(xiàn)1785條經(jīng)驗(yàn) 獲得超4個(gè)贊

由于這似乎是家庭作業(yè)，因此我將提出一些建議，但不會(huì)給出完整的解決方案：

您當(dāng)前的代碼正在重復(fù)索引檢查。例如，您正在循環(huán)索引 [0,1] 和 [1,0]，因?yàn)?a+b = b+a，它們的總和總是相同的。相反，我建議你的循環(huán)i從 0 到 len-1，你的循環(huán)j從 i+1 到 len-1。這樣，您將永遠(yuǎn)不會(huì)重復(fù)檢查。
您當(dāng)前檢查的一部分包括條件nums[i] != nums[j]，但您的問題并未說明數(shù)組中的兩個(gè)值不能相同。toSum([1, 4, 4], 8)是否可以使用4+4=8 之類的值調(diào)用此函數(shù)？如果是這樣，那么您可以刪除nums[i] != nums[j]檢查以節(jié)省時(shí)間。
目前尚不清楚提供的數(shù)組是否已排序。如果不是，那么您可以創(chuàng)建一個(gè)跟蹤變量來說明您已經(jīng)檢查過的值，并防止在未來的迭代中檢查它們。例如，如果您已經(jīng)將值 4 與數(shù)組中的所有其他值進(jìn)行了比較，但沒有找到解決方案，那么如果您稍后在數(shù)組中遇到 4，則沒有理由檢查它。

反對(duì) 回復(fù) 2022-05-26

梵蒂岡之花

TA貢獻(xiàn)1900條經(jīng)驗(yàn) 獲得超5個(gè)贊

你可以隨著時(shí)間的推移解決這個(gè)問題O(n)。這種方法解決的條件是數(shù)組必須排序。

let twosum = (arr, x) => {

let s = 0,

e = arr.length - 1;

let loc = [];

while (s < e) {

if (arr[s] + arr[e] === x) {

loc.push([s,e]);

s++;

e--;

} else if (arr[s] + arr[e] < x) {

s++;

} else {

e--;

}

return loc;

};

console.log(twosum([1, 2, 3, 4, 5, 7, 8], 9));

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

如果有人感興趣，這背后的算法：

1. Set s value as 0

2. Set e value as last index say (arr.length - 1)

3. While s is less than e i.e not pass one another

4. 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 value

4.2. decrement e value by 1 as there is no possibility to find any combination after the current e value

4.3. collect the indexes where the match found.

5. If arr[s] + arr[e] < x

5.1 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. If arr[s] + arr[e] > x

6.1 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.

反對(duì) 回復(fù) 2022-05-26