solve twosum in csharp

The Two Sum problem in C# can be solved using various techniques but I am going to explain two approaches: Brute Force and HashMap.

Brute Force Approach

The Brute Force approach is to iterate through each element of the array (from beginning to end) and search for a complementing element that will add up to the given sum. We will require two nested loops to check each possible combination of elements.

main.cs
public static int[] TwoSum(int[] nums, int target) 
{
    for(int i=0;i<nums.Length;i++)
    {
        for(int j=i+1;j<nums.Length;j++)
        {
            if(nums[i]+nums[j]==target)
                return new int[] {i,j};
        }
    }
    throw new ArgumentException("No two sum solution");
}
300 chars
13 lines

HashMap Approach

The HashMap approach uses a hashtable to store the elements of the array and their corresponding indices.

main.cs
public static int[] TwoSum(int[] nums, int target) 
{
    Dictionary<int,int> map = new Dictionary<int,int>();
    for(int i=0;i<nums.Length;i++)
    {
        if(map.ContainsKey(target-nums[i]))
            return new int[] { map[target-nums[i]], i };
        else if(!map.ContainsKey(nums[i]))
            map.Add(nums[i],i);
    }
    throw new ArgumentException("No two sum solution");
}
392 chars
13 lines

In this approach, we iterate through each element of the array and check if the complementing element (i.e. target-nums[i]) is present in the hashtable. If it is present, we return its corresponding index along with the current index. If it isn't present, we add the element and its index to the hashtable.

Both approaches have a time complexity of O(n^2) and O(n) respectively. The HashMap approach is more efficient for larger arrays as it has a linear time complexity and requires only a single pass through the array.