javascript hackerranks sherlock 和数组性能问题

Question

Watson gives Sherlock an array A of length N. Then he asks him to determine if there exists an element in the array such that the sum of the elements on its left is equal to the sum of the elements on its right. If there are no elements to the left/right, then the sum is considered to be zero. Formally, find an i, such that,

Input Format

The first line contains T, the number of test cases. For each test case, the first line contains N, the number of elements in the array A. The second line for each test case contains N space-separated integers, denoting the array A.

Constraints

1<=T<=10
1<=N<=10^5
1<=Ai<=2*10^4
1<=i<=N

Output Format

For each test case print YES if there exists an element in the array, such that the sum of the elements on its left is equal to the sum of the elements on its right; otherwise print NO.

Sample Input

2 
3
 1 2 3

4
 1 2 3 3

Sample Output

NO 
YES

Explanation

For the first test case, no such index exists. For the second test case,

therefore index 3 satisfies the given conditions.

我在 3 个测试用例上遇到超时问题

 function check(input) {
    var result = "NO";
    var sum=0;
    input.map(function(data){
        sum=sum+(+data);
    })
    sumLeft=0;
    sumRight=sum-(+input[0]);

    for(var i=1;i<input.length;i++){
        sumLeft=sumLeft+(+input[i-1]);
        sumRight=sumRight-(+input[i])
        if(sumLeft==sumRight)
        {
            console.log("YES");
            return;
        }
    }
    console.log("NO");
}

function processData(input) {
    //Enter your code here
    var lines = input.split("\r\n");
    for (var m = 2; m < lines.length; m = m + 2) {
        check(lines[m].split(" "));
    }
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function(input) {
    _input += input;
});
process.stdin.on("end", function() {
    processData(_input);
});

Answer 1

遍历数组一次以找到总和。声明两个变量:sumLeft 和 sumRight。 sumLeft 的初始值应为 0，sumRight 的初始值应为 totalSum-arr[0]。

再次遍历数组，将 sumLeft 递增 (n-1) 个元素，将 sumRight 递减第 n 个元素。继续比较两个变量以检查它们是否彼此相等。您将时间复杂度降低到 O(n)

以下代码在 https://www.hackerrank.com/challenges/sherlock-and-array 上通过了测试.棘手的部分是为数组长度为 1 时设置默认响应。我承认 @trincot 的答案对于仅包含正整数的数组更有效(n 而不是 2n)。

 function check(input) {
    var result = "NO";
    var sum=0;

     if(input.length == 1){
        console.log("YES");
        return;
     }

    input.map(function(data){
        sum=sum+(+data);
    })
    sumLeft=0;
    sumRight=sum-(+input[0]);

    for(var i=1;i<input.length-1;i++){
        sumLeft=sumLeft+(+input[i-1]);
        sumRight=sumRight-(+input[i])
        if(sumLeft==sumRight)
        {
            console.log("YES");
            return;
        }else if (sumLeft>sumRight) {  ///worked both with and without this optimization
            console.log("NO"); 
            return;
        }
    }
    console.log("NO");
}



function processData(input) {

    //var lines = input.split("\r\n");
    var lines = input.split(/\r|\n/)
    for (var m = 2; m < lines.length; m = m + 2) {
        check(lines[m].split(" "));
    }
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function(input) {
    _input += input;
});
process.stdin.on("end", function() {
    processData(_input);
});