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]

Example 3:

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

Constraints:

• 2 <= nums.length <= 10<sup>4</sup>

• -10<sup>9</sup> <= nums[i] <= 10<sup>9</sup>

• -10<sup>9</sup> <= target <= 10<sup>9</sup>

• Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less thanO(n<sup>2</sup>) time complexity?

Hint

A really brute force way would be to search for all possible pairs of numbers but that would be too slow. Again, it's best to try out brute force solutions for just for completeness. It is from these brute force solutions that you can come up with optimizations.

So, if we fix one of the numbers, say x, we have to scan the entire array to find the next number y which is value - x where value is the input parameter. Can we change our array somehow so that this search becomes faster?

The second train of thought is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?

Solution

public class Solution {

  public int[] TwoSum(int[] nums, int target) {

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

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

      int complement = target - nums[iCt];

      if (complements.ContainsKey(complement)) {
        return new int[] { complements[complement], iCt };
      }

      // Check if the complement is already present in the dictionary
      if (!complements.ContainsKey(nums[iCt])) {
        complements.Add(nums[iCt], iCt);
      }
    }

    throw new ArgumentException("No Solution Found");
  }
}

Explanation

Imagine you have a list of numbers (called nums), and you want to find two numbers in that list that add up to a specific target number. The given code helps you do that efficiently.

Here's how it works:

1. One-pass Hash Table: This is like a special tool (hash table) that helps us organize and look up numbers quickly.

2. Algorithm: Think of it as a set of instructions or steps to solve the problem.

3. One-pass: It means we go through the list of numbers only once, not multiple times.

4. Hash Table: Imagine a table where you can quickly find things. In our case, it's like a table that stores numbers and helps us find them faster.

5. Code Explanation:

   • We create a special table called "complements" using the code Dictionary<int, int> complements = new Dictionary<int, int>();.

   • We then go through each number in the list (for (int iCt = 0; iCt < nums.Length; iCt++)).

   • For each number, we calculate its complement (another number that, when added to it, gives the target) using int complement = target - nums[iCt];.

   • We check if this complement is already in our table. If it is, that means we found two numbers that add up to the target, and we return their positions in the list.

   • If the complement is not in the table, we add the current number and its position to the table.

   • If we go through the whole list and don't find a solution, we say, "No Solution Found."

In simple terms, it's like looking at each number once, checking if there's another number in the list that, when added to it, gives the target. If we find it, we tell which two numbers in the list make up the target. If we don't find any, we say there's no solution.