I solved this problem by iterating through the array then find the item when the sum equals to array[i] item returning true otherwise returning false.

My Question is => How I can return the indices of those numbers that add up to sum not just true? Using the same code below:

function hasPairsWithSum(array,sum) {
  for (let i = 0; i < array.length; i  ) {
    if (array.find((item) => {return sum === array[i]   item}
    ));
    return true;
  };
  return false;
};
console.log(hasPairsWithSum([1,2,4,4],8))

Note: Time complexity must be less than O(n ^ 2).

CodePudding user response：

You have to iterate over the array elements checking at every iteration for every element of the array (except the last one) all the elements at the right of it like below:

function findIndexes(array, sum) {
    const result = [];

    for (let i = 0; i < array.length -1;   i) {
        for (let j = i   1; j < array.length;   j) {
            if ((array[i]   array[j]) === sum)  {
                result.push([i, j]);
            }
        }
    }

    return result;
}

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

CodePudding user response：

Please refer this code.

function hasPairsWithSum(array,sum) {
    let result = [];
  for (let i = 0; i < array.length; i  ) {
    if (array.some((item, index) => {return i === index ? false : sum === array[i]   item}))
        result.push(i);
  };
  return result;
};
console.log(hasPairsWithSum([1,2,4,4],8))
console.log(hasPairsWithSum([3,2,4],6))
console.log(hasPairsWithSum([0,4,3,0],0))

CodePudding user response：

O(n) Soln ... using math concept a b = n then if a is present in aur array then need to find b = n - a is present or not ..

def hasPairsWithSum(array,sum):
    d = {} 
    for i in range(len(array)):
        if(array[i] in d):
            d[array[i]].append(i)
        else:
            d[array[i]] = [i]
    ans  = []
    for i in range(len(array)):
        val = sum - array[i]
        if(val in d):
            if(d[val][0] == i):
                if(len(d[val])  > 1):
                    ans.append((i,d[val][1]))
                    break
                else:
                    continue
            else:
                ans.append((i,d[val][0]))
                break
    return ans
print(hasPairsWithSum([4, 4, 4, 4], 8))

O(nlogn) soln ....just store the index with elements .. then sort it by their values .. next step run a loop with complexity of O(n) [concept : Two pointers]

def hasPairsWithSum(array,sum):
    arr = []
    for i in range(len(array)):
        arr.append((array[i],i))
    arr.sort()
    i = 0
    j = len(array)-1
    ans = []
    while(i<j):
        tmp_sum = arr[i][0]   arr[j][0]
        if(tmp_sum == sum):
            ans.append((arr[i][1] , arr[j][1]))
            #add your logic if you want to find all possible indexes instead of break
            break
        elif(tmp_sum < sum):
            i = i   1
        elif(tmp_sum > sum):
            j = j - 1
    return ans
print(hasPairsWithSum([1,2,4,4],8))

• note : if you want to find all possible soln then this approach will not work either add you own logic in while loop or another approach is use binary search with traversal on every element and store the indexes in set (worst case this will be O(n^2) as we have to find all possible values) Eg: [4,4,4,4,4,4] , sum = 8 and you want to print all possible indexes then we end up running it upto n^2 (why? reason: total possible solns. are 5 4 3 2 1 = n*(n-1)/2 ≈ n^2)