Give an O(n^2) algorithm to solve

Question

This is my homework question

Given an array A[1..n] of n integers, we want to decide if there exist i and j, where 1 ≤ i , j ≤ n, such that A[i] + A[j] = α for a given value α.

Give an O(n^2) algorithm to solve the problem.

Can anyone understand what the question like to ask?

Answer 1

This problem is called two-sum you should return indices of the two numbers such that they add up to the target.

let's say you have an array called nums = [2,7,11,15] and the target = 9, you should find two indices of two numbers in this example will be

num[0] + num[1] => 2+7 = 9 which is the target

There are two different approaches to solve it, first by brute force and the time complexity will be o(n ^ 2)

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

and the second approach by using Hash-table and the time complexity will be o(n) and it's absolutely better

var twoSum = function(nums, target) {
    const indices = new Map();

    for (let index = 0; index < nums.length; index++) {
        const complement = target - nums[index];

        if (indices.has(complement)) {
            return [indices.get(complement), index]
        }

        indices.set(nums[index], index)
    }
};

Note: This solution by using JS language you can write it with any language, just you should understand the problem and the idea of solution and you'll be able to write it with any language you want.