Solve Two Sum in C#: From Brute Force to Hash Maps

01 / Understand the problem

Given an array of integers and a target, return two distinct indices whose values sum to the target. Return an empty array when no pair exists. Assume all input values and arithmetic fit a signed 32-bit integer.

nums = [2, 7, 11, 15], target = 9 gives [0, 1]. You must not reuse the same index.

02 / Think before coding

Write down every pair you could examine. What information would let you avoid searching the rest of the array for each number?

03 / Design the solution

Walk from left to right. For each value, compute its complement. If the dictionary already contains that complement, return its stored index and the current index. Otherwise, remember the current value.

seen = empty map
for each index i:
  complement = target - nums[i]
  if seen contains complement: return [seen[complement], i]
  seen[nums[i]] = i
return []

04 / Implement

public static int[] TwoSumBrute(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[] { i, j };
    return Array.Empty<int>();
}

public static int[] TwoSum(int[] nums, int target)
{
    var seen = new Dictionary<int, int>();
    for (int i = 0; i < nums.Length; i++)
    {
        int complement = target - nums[i];
        if (seen.TryGetValue(complement, out int previous))
            return new[] { previous, i };
        seen[nums[i]] = i;
    }
    return Array.Empty<int>();
}

05 / Test the contract

TwoSum(new[] { 2, 7, 11, 15 }, 9); // [0, 1]
TwoSum(new[] { 3, 3 }, 6); // [0, 1]
TwoSum(new[] { -3, 4, 3 }, 0); // [0, 2]
TwoSum(new[] { 1 }, 2); // []
TwoSum(Array.Empty<int>(), 0); // []

06 / Improve

Decide how to handle integer overflow and null input. For unbounded int inputs, compute the complement using long and validate before converting. If multiple pairs exist, document which one is returned. Sorting can reduce auxiliary storage in some variants, but preserving original indices changes the tradeoff.

07 / Compare with AI

Ask an assistant to solve the same contract. Check duplicate values, same-index reuse, overflow assumptions, and complexity claims yourself. Passing the first example is not a proof of correctness.