Skip to content

1. Two Sum

Easy

Description

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 <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

Solutions

Approach 1: Hash Table

Time complexity: \(O(n)\)

Space complexity: \(O(n)\)

Notes

We can use the hash table seen to store the array value and the corresponding index.

Traverse the array nums, when you find target - nums[i] in the hash table, it means that the target value is found, and the index of target - nums[i] and i are returned.

The time complexity is O(n) and the space complexity is O(n). Where nis the length of the array nums.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {} #map elements with their indexs {ele:idx}
        for idx,ele in enumerate(nums):
            num = target - ele
            if num in seen:
                return [seen[num],idx]
            seen[ele] = idx

class Solution {
    public int[] twoSum(int[] nums, int target) {
    }
}

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {

    }
};

func twoSum(nums []int, target int) []int {
}

function twoSum(nums: number[], target: number): number[] {
    const seen = new Map();

    for (let i = 0;i < nums.length; i++){
        const diff = target - nums[i]

        if (seen.has(diff)){
            return [seen.get(diff),i]
        }

    seen.set(nums[i],i)
    }

}

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {

    }
}

/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {}

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
    }
}

class Solution {
    /**
    * @param Integer[] $nums
    * @param Integer $target
    * @return Integer[]
    */
    function twoSum($nums, $target) {
    }
}

object Solution {
    def twoSum(nums: Array[Int], target: Int): Array[Int] = {
    }
}

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {

    }
}

# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}
def two_sum(nums, target)

end

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {

    }
}

proc twoSum(nums: seq[int], target: int): seq[int] =

class Solution {
    func twoSum(nums: Array<Int64>, target: Int64): Array<Int64> {

    }
}