Two Sum easy

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 1:

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

Example 2:

Input: nums = [3,2,4], target = 6 Output: [1,2]

Steps

1. Create a Dictionary: We'll use a dictionary (hash table) to store each number in nums along with its index. The key will be the number, and the value will be its index.

2. Iterate Through the Array: We iterate through the nums array. For each number:

   • Calculate the Complement: We calculate the complement needed to reach the target. This is target - currentNumber.
   • Check the Dictionary: We check if the complement exists as a key in the dictionary.
     • If Found: If the complement is found, it means we've found the pair. We return the index of the current number and the index stored in the dictionary for the complement.
     • If Not Found: If the complement is not found, we add the current number and its index to the dictionary.

3. No Solution: If the loop completes without finding a pair, it means there's no solution (though the problem statement guarantees a solution).

Explanation

The use of a dictionary (hash table) makes this solution very efficient. Looking up a key in a dictionary takes, on average, O(1) time. This contrasts with a brute-force approach that would require nested loops, resulting in O(n²) time complexity.

Code

using System;
using System.Collections.Generic;

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        Dictionary<int, int> numMap = new Dictionary<int, int>(); // Dictionary to store number and its index

        for (int i = 0; i < nums.Length; i++) {
            int complement = target - nums[i];
            if (numMap.ContainsKey(complement)) {
                return new int[] { numMap[complement], i }; // Found the pair
            }
            numMap[nums[i]] = i; // Add the current number and its index to the dictionary
        }

        return new int[] { }; // Should not reach here according to problem statement
    }
}

Complexity

• Time Complexity: O(n), where n is the length of the nums array. We iterate through the array once. Dictionary lookups are on average O(1).
• Space Complexity: O(n) in the worst case, as the dictionary could store all the numbers from the input array.