How can I optimize for loop?-CodePudding

I want to optimize the time complexity of this code. Now, code has O(n^2) complexity. How can I reduce complexity? input is unsorted array and target, output is true or false.

Here`s my code.

// pseudo code in js
function find(arr, target) {
    for(let i = 0; i < arr.length; i  ){
        for(let j = i   1; j < arr.length; j  ){
            if(target === (arr[i] arr[j])){
                return true;
            }
        }
    }
    return false;
}

I think hint is unsorted array. And I don`t know at all..

CodePudding user response：

I don't think your particular implementation can be simplified, however if you first sort the array you can take a two-pointer approach to figure out if the target can be found, resulting in O(n log n) complexity.

function find(arr, target) {
    arr.sort();
    let start = 0;
    let end = arr.length - 1;
    while(start < end) {
        if(arr[start]   arr[end] > target) {
            end--;
        } else if(arr[start]   arr[end] < target) {
            start  ;
        } else {
            return true;
        }
    }
    return false;
}