[LeetCode] Two Sum

#1.Two Sum

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]

Example 3

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

Explanation

Find two numbers in the given array that add up to target, and return their index.

• Only one valid answer.
• The element will not be used twice.

Solution

A more intuitive way to solve this is by using a double loop to iterate through the array. This brute-force solution requires more time when the data size is large.

If we consider time complexity, we should reduce the number of loop iterations to drastically reduce execution time. We can use an additional space to store elements, thus implementing the space-for-time idea. Although this method reduces time complexity, it also increases space complexity.

• Array

By iterating through the array using a double loop, and since elements can't be reused, we start from i+1 to skip the current element and previously checked values.

  public int[] TwoSum(int[] nums, int target)
  {
        int i, j;

        for (i = 0; i < nums.Length; i++)
            for (j = i + 1; j < nums.Length; j++)
                if (nums[i] + nums[j] == target)
                    return new int[] { i, j };

        return null;
  }

• HashTable

Use an additional space with a HashTable to achieve the space-for-time approach.

  public int[] TwoSum(int[] nums, int target)
  {
      Hashtable hash = new Hashtable();

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

          if (hash.ContainsKey(diff))
              return new int[] { i, (int)hash[diff] };

          if (!hash.ContainsKey(num))
              hash.Add(num, i);
      }

      return null;
  }

• Dictionary

Similarly, use an additional space with a Dictionary to achieve space-for-time approach.

  public int[] TwoSum(int[] nums, int target)
  {
      Dictionary<int, int> dic = new Dictionary<int, int>();

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

          if (dic.ContainsKey(diff))
              return new int[] { i, (int)dic[diff] };

          if (!dic.ContainsKey(num))
              dic.Add(num, i);
      }

      return null;
  }

Job done☑️

---

Thanks for reading the article

If you like it, please don't hesitate to click heart button ❤️
or follow my GitHub I'd appreciate it.

---