Two Sum Problem: Finding the Indices for Target Sum in an Integer Array

We will explore an efficient solution to the classic "Two Sum" problem using C#. Given an array of integers and a target value, our goal is to find the indices of two numbers that add up to the target. We will walk through a concise and optimized algorithm, accompanied by an implementation in C#.

 

Example:

Let's consider the following scenario to illustrate the Two Sum problem. 

Given the array `nums = [2, 7, 11, 15]` and the `target = 9`, we need to find two numbers in the array that add up to the target.

For the provided input, the expected output is indices = [0, 1], indicating that the numbers at indices 0 and 1 in the array nums (2 and 7, respectively) add up to the target value of 9.

Code Implementation:

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        Dictionary complementMap = new Dictionary();
        int[] result = new int[2];

        for (int i = 0; i < nums.Length; i++) {
            int complement = target - nums[i];

            if (complementMap.ContainsKey(complement)) {
                result[0] = complementMap[complement];
                result[1] = i;
                return result;
            }
            else if (!complementMap.ContainsKey(nums[i])) {
                complementMap.Add(nums[i], i);
            }
        }

        return result;
    }
}

Explanation:

1. We start by initializing a dictionary called complementMap to store the complement of each number encountered in the array.
2. We create a result array to hold the indices of the two numbers that add up to the target.
3. Next, we iterate through the array using a for loop.
4. For each number at index i, we calculate the complement by subtracting the current number from the target.
5. We check if the complementMap contains the complement. If it does, we have found our solution.
6. We assign the index of the complement (stored in the complementMap) to result[0].
7. We assign the current index i to result[1].
8. We return the result array.
9. If the complement is not found in the complementMap, we check if the current number is already present as a key in the complementMap. If not, we add it to the complementMap with its index as the value.
10. If no solution is found after iterating through the entire array, we return the default result array with both indices set to 0.

1.