1

Brute force is simple. For every element, we try to add every other element and if sum is equal to target, we have found the answer.

This is $O(n^2)$, because for every element we check all other elements.

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        //Brute Force O(n^2)
 
        for (int i = 0; i < nums.Length; i++)
        {
            for (int j = i + 1; j < nums.Length; j++)
            {
                    if ((long)nums[i] + nums[j] == target)
                    {
                        return new int[] {i, j};
                    }
            }
        }
 
        return Array.Empty<int>();
    }
}

Things to note,
We started inner j loop from i + 1, instead of 0. Because we can skip checking elements to the left since that particular comparison would have happened already. Also, we avoid the check for i != j this way.

Second, in contraints it is given target is $<=10^9$, but when adding the numbers inside if, we cannot assume all additions will respect that, so we are casting one element to long, which makes the sum long as well, for overflow safety. It’s just on the boundary, so just to be on a safer side.

You see, approx max value for int is $2.1\cdot 10^9$, while for long it is $9.22\cdot 10^{18}$.

---

Now, optimal solution $O(n)$,

Thing is, we want one pass through the array, and for each element, we will ask do I have the required number? And to search the required number, we will search in dict (which grows as we move ahead). Moving ahead, and asking ‘have I seen this before’, this points to using a hashset or dict.

The ‘Have I seen this before’ value, we are able to get via already given target by subtracting.

And since the pairs are commutative, it works well for one pass and growing dict. Commutative in the sense, that pair $(i,j)$ and $(j,i)$ have no difference for us, whether we find it in $i^{th}$ loop or $j^{th}$ loop.

And we use dict[key] = value syntax because it doesn’t throw if key already present, it will overwrite. Otherwise we would done if not contains key, then only add.

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        var dict = new Dictionary<int, int>();
        for (int i = 0; i < nums.Length; i++)
        {
            var complement = target - nums[i];
            if (dict.ContainsKey(complement))
            {
                return new int[] {dict[complement], i};
            }
            dict[nums[i]] = i;
        }
        return Array.Empty<int>();
    }
}

Another important thing,
We check first, then add, so we never match an element with itself. By the time we search for a complement, only elements before the current index are in the dict.

In this optimal solution, we used a dictionary, which can grow to size n, so space complexity for this solution is $O(n)$.