Javascript twoSum 算法 : Given an array of integers, 返回两个数字的索引，以便它们加起来达到特定目标

Question

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

Example:

Given nums = [3, 2, 4], target = 6,

Because nums[1] + nums[2] = 2 + 4 = 6

return [1, 2].

解决方案

var twoSum = function(nums, target) {
    for(let i = 0; i <= nums.length; i++){
        for(let j = 0; j <= nums.length; j++){
            if(nums[i] + nums[j] == target){
                return [i, j]
            }
        }
    }
};

上面的代码适用于其他情况，但不适用于这种情况。

预期结果 [1,2]

输出 [0,0]

例如，我尝试使用不同的数字数组和不同的目标，即使您更改数字的顺序也能正常工作

示例:

新数组:[15, 7, 11, 2], target = 9,

输出: [1, 3]。

我不明白解决方案有什么问题，希望有人能解释一下。谢谢

Answer 1

你可以使用一个非常简单的技术。
基本上，您可以检查数组中是否存在目标和当前迭代中的元素的差异。

假设同一个索引不能被使用两次

nums = [3, 2, 4], target = 6
nums[0] = 3
target = 6
diff = 6 - 3 = 3
nums.indexOf[3] = 0 // FAILURE case because it's the same index

// move to next iteration
nums[1] = 2
target = 6
diff = 6 - 2 = 4
nums.indexOf(4) = 2 // SUCCESS '4' exists in the array nums
// break the loop

这是 leetcode 接受的答案.

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    for (let index = 0; index < nums.length; index++) {
        const diff = target - nums[index];
        const diffIndex = nums.indexOf(diff);
        // "diffIndex !== index" takes care of same index not being reused
        if (diffIndex !== -1 && diffIndex !== index) {
            return [index, diffIndex];
        }
    }
};

运行时间:72 毫秒，比 Two Sum 的 93.74% JavaScript 在线提交快。
内存使用:38.5 MB，Two Sum 的 JavaScript 在线提交不到 90.55%。

有人能帮我减少内存使用量吗？