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(n^2)\) time complexity?

Solutions ๐Ÿ”“

Video Solution Coming Soon

Approach 1: Hash Table

Time complexity: \(O(n)\)

Space complexity: \(O(n)\)

Way 1

Algorithmic

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 \(n\) is the length of the input 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) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        return null;
    }
}

/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {

}

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> indices;
        for (int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i];
            if (indices.count(complement)) {
                return {indices[complement], i};
            }
            indices[nums[i]] = i;
        }
        return {};
    }
};

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);
    }
    return [];
}

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> {

    }
}
Akhil Singh Chauhan Akhil Singh Chauhan
Creator

Comments