Problem Statement

Given an integer array nums and an integer target, find the indices of the two numbers such that they add up to the target. Each input will have exactly one solution, and the same element cannot be used twice. Return the answer as a tuple or array of indices. ### Examples

Input: nums = [2,7,11,15], target = 9
Output: [0,1]

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

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

Brute Force Approach

Initially, one might consider a nested loop approach, similar to bubble sort logic. This method checks every possible pair of elements in the array to see if they sum to the target. `C# Example:````

public static (int, int) BruteForceTwoSum(int[] nums) { int target = 9; for (int i = 0; i < nums.Length; i++) { for (int j = i + 1; j < nums.Length; j++) { if (nums[i] + nums[j] == target) { return (i, j); } } } return (0, 0); // fallback if no pair found }

This brute force method has a time complexity of **O(n²)**, which is inefficient for large arrrays. ### Optimized Hash Table Approach

To improve performance, we can use a hash table (dictionary-like structure) for constant-time lookups. In C#, the `Hashtable` class can be used, although `Dictionary<int, int>` is often preferred for type safety and performance. `C# Example Using Hashtable:````

public static (int, int) HashBasedTwoSum(int[] nums, int target = 9)
{
    Hashtable indexMap = new Hashtable();
    
    for (int i = 0; i < nums.Length; i++)
    {
        int complement = target - nums[i];
        
        if (indexMap.ContainsKey(complement) && 
            (int)indexMap[complement] != i)
        {
            return ((int)indexMap[complement], i);
        }

        if (!indexMap.ContainsKey(nums[i]))
        {
            indexMap.Add(nums[i], i);
        }
    }
    
    return (0, 0); // fallback if no pair found
}

This approach has a time complexity of O(n), as each element is processed exact once with constant-time hash lookups. ### Data Structure Considerations

While HashSet is useful for set operations like union and intersection, it doesn't store value-to-key mappings, making it unsiutable for this specific problem. The Dictionary or Hashtable provides both fast lookups and key-value storage needed for this solution. ### Performance Summary

• Brute Force: O(n²) time complexity, O(1) space
• Hash Table: O(n) time complexity, O(n) space