javascript - 有没有更有效的方法来编码这个“2 Sum”问题

Question

给定一个整数数组，找到两个数字，使它们加起来等于一个特定的目标数字。

函数 twoSum 应该返回两个数字的索引，以便它们相加到目标，其中 index1 < index2。请注意，您返回的答案（ index1 和 index2 ）不是从零开始的。将这两个数字按顺序放入一个数组中，然后从您的函数中返回该数组（查看函数签名会使事情更清楚）。请注意，如果不存在对，则返回空列表。

如果存在多个解决方案，则输出 index2 最小的那个。如果有多个具有最小 index2 的解决方案，请从中选择具有最小 index1 的解决方案。

twoSum : function(A, B){
        var tempA = A;
        var index1 = [];
        var index2 = [];
        var Results = [];
        var diff = A.length/2;
        
        for(var i = 0; i < A.length - 1; i++){
            var temp = B - A[i];
            for(var j = i; j < A.length - 1; j++){
                if(temp == A[j]){
                    if(j - i > 0){
                        if(j < Results[1] || Results.length == 0){
	                    	if(A[j] != A[Results[1]-1] && A[i] != A[Results[0]-1]){
	                    		Results[0] = i + 1;
	                            Results[1] = j + 1; 
	                    	}
                        }
                    }
                }
            }
        }
        return Results;
    }

标签： javascript

Answer 1

您可以对对象采用单循环方法来存储缺失值。

function find(array, sum) {
    var hash = {},
        i = 0;
        
    while (i < array.length) {
        const value = array[i++];
        if (value in hash) return [hash[value], i];
        if (!(sum - value in hash)) hash[sum - value] = i;
    }
}

console.log(find([2, 4, 2, 3, 7, 6, 5, 3, 4], 8));