Skip to content

1 The sum of two numbers ✅

Leetcode

::: tip Key points 💡

  • Convert summation to difference
  • Correspond to each element and its index in the array with the help of the Map structure
  • Exchange space for time, reduce the search time from O(N) to O(1) :::

Title description

Given an integer array nums and a target value target, please find the two integers whose sum is the target value in the array and return their array subscripts.

You can assume that each input will only correspond to one answer. However, you cannot reuse the same elements in this array.

Example:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: 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]

Pre-knowledge

-Hash table

Ideas

The easiest thing to think of is brute force enumeration. We can use a two-layer for loop to traverse each element and find the target element that meets the conditions. However, the time complexity is O(N^2), the space complexity is O(1), and the time complexity is high. We have to find ways to optimize.

Here we can add a Map to record the number that has been traversed and its corresponding index value. In this way, when traversing a new number, go to the Map to query whether the difference between the target and the number has already appeared in the previous number. If it appears, the answer is found, and there is no need to continue execution.

C# Solution

// Given an array of integers, return indices of the two numbers such that they add up to a specific target.
// You may assume that each input would have exactly one solution, and you may not use the same element twice.

// Example:
// Given nums = [2, 7, 11, 15], target = 9,
// Because nums[0] + nums[1] = 2 + 7 = 9,
// return [0, 1].

using System.Collections.Generic;

namespace Algorithms.Simple
{
  public class TwoSum
  {
    public static int[] Evaluate(int[] nums, int target)
    {
      var subtractedDictionary = new Dictionary<int, int>();
      var result = new int[2];

      for (var i = 0; i < nums.Length; i++)
      {
        var num = nums[i];
        if (!subtractedDictionary.ContainsKey(num))
        {
          subtractedDictionary[target - num] = i;
        }
        else
        {
          result = new int[] { subtractedDictionary[num], i };
        }
      }

      return result;
    }
  }
}

C# Tests

using Algorithms.Simple;
using Xunit;

namespace AlgorithmTests.Simple
{
  public class TwoSumTests
  {
    [Fact]
    public void EvaluateTrue1()
    {
      Assert.Equal(new int[] { 0, 1 }, TwoSum.Evaluate(new int[] { 2, 7, 11, 15 }, 9));
    }

    [Fact]
    public void EvaluateTrue2()
    {
      Assert.Equal(new int[] { 1, 2 }, TwoSum.Evaluate(new int[] { 3, 2, 4 }, 6));
    }
  }
}

JS Solution

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = function(nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const diff = target - nums[i];
    if (map.has(diff)) {
      return [map.get(diff), i];
    }
    map.set(nums[i], i);
  }
};

Complexity Analysis

-Time complexity: \(O(N)\) -Space complexity: \(O(N)\)

For more solutions, please visit my LeetCode solution repository: https://github.com/azl397985856/leetcode. Currently it has 37K stars.

Pay attention to the official account and try to restore the problem-solving ideas in clear and straightforward language, and there are a lot of illustrations to teach you to identify routines and to efficiently solve the problems.