Bamiji Oyetubo

Posted on

Two Sum in C#

Today, we will be solving the famous two sum leetcode problem in C#.

I've decided to do this since I don't see many DSA solutions in C# online, so let's dive in.

The problem statement: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example: Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

To solve this problem, we'll be making use of the Dictionary (also known as map)

First we initialize our dictionary with a Key of Int and a Value of int

Dictionary<int,int> map = new Dictionary<int,int>();

Next, we want to loop over the nums array

for(int i = 0; i < nums.Length; i++)

and then initialize an integer that will be set to the target number minus the particular array index we are on, this will look something like this

int num = k - nums[i];

What we do next is to check if the number we got from the substraction above is present in our dictionary. The way we do that in C# is the TryGetValue method, which takes two parameters:
1. The key we are searching for. In our case that will be num if it exists
2. The out value which will be the value of key num . we'll call this variable index
The method will return true if num exists in our map and assign the out value to the variable we specified. If it does exist, we simply return the the index i and the variable index since both these positions in our array sum up to our target.

if (map.TryGetValue(num, out int index))
{
return new int[] { i, index };
}

If the key num does not exist in our dictionary, we simply replace our map key with int from our array at the index that we are currently on and then assign the value to be the index i itself,

else map[nums[i]] = i;

ps: we dont want to do a map.Add, as that will mean we have to iterate over the map again

Next we exit the for loop and return an array of size two with default values of zero if none of the numbers sum up to our target.

return new int[2];

Coming together, everything should look like this

public static int[] TwoSumUnsorted(int[] nums, int target)
{
Dictionary<int,int> map = new Dictionary<int,int>();

for(int i = 0; i < nums.Length; i++)
{
int num = target - nums[i];
if (map.TryGetValue(num, out int index))
{
return new int[] { i, index };
}
else map[nums[i]] = i;
}
return new int[2];
}

Thanks for reading, I look forward to solving more leetcode( and general Algorithmic) problems using C# in the future. Happing coding.