Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/1.html
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?
Algorithm
In general, increasing time complexity comes at the cost of using more space, creating a trade-off. However, in this particular problem, I aim to achieve linear time complexity by only traversing the array
once and using a HashMap
to establish a mapping between each number
and its coordinate position
.
Since the search efficiency of a HashMap
is constant, while traversing the array
, we can subtract the current number
from the target
to find the other number
needed. We can then look up this other number
directly in the HashMap
. Note that the number
found may not be the immediate preceding number
. For example, if the target
is 4 and we have traversed a 2, the other number
needed may not be the previous number
, which is also 2.
The implementation steps for this approach are as follows: first traverse the array
to create the HashMap
mapping, and then traverse it again to search for the target
numbers
and record their indices
.
Code
-
import java.util.HashMap; class Two_Sum { public static void main(String[] args) { Two_Sum out = new Two_Sum(); Solution s = out.new Solution(); int[] a = {2, 7, 11, 15}; int target = 9; int[] result = s.twoSum(a, target); for (int each : result) { System.out.println(each); } } // time: O(N) // space: O(N) public class Solution { public int[] twoSum(int[] nums, int target) { // set up hashmap: remaining to original. thread-unsafe but for here is ok HashMap<Integer, Integer> hm = new HashMap<>(); for (int i = 0; i < nums.length; i++) { // if key in hm, result found. // so that only one pass if (hm.containsKey(nums[i])) { int otherIndex = hm.get(nums[i]); return new int[]{Math.min(i, otherIndex) + 1, Math.max(i, otherIndex) + 1}; } // put new record into hashmap else { hm.put(target - nums[i], i); } } return null; } } } ############ class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> m = new HashMap<>(); for (int i = 0;; ++i) { int x = nums[i]; int y = target - x; if (m.containsKey(y)) { return new int[] {m.get(y), i}; } m.put(x, i); } } }
-
// OJ: https://leetcode.com/problems/two-sum/ // Time: O(NlogN) // Space: O(N) class Solution { public: vector<int> twoSum(vector<int>& A, int target) { vector<vector<int>> v; int N = A.size(), L = 0, R = N - 1; for (int i = 0; i < N; ++i) v.push_back({ A[i], i }); sort(begin(v), end(v)); while (L < R) { int sum = v[L][0] + v[R][0]; if (sum == target) return { v[L][1], v[R][1] }; if (sum < target) ++L; else --R; } return {}; } };
-
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: m = {} for i, v in enumerate(nums): x = target - v if x in m: return [m[x], i] m[v] = i ############ class Solution(object): def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ d = {} for i, num in enumerate(nums): if target - num in d: return [d[target - num], i] d[num] = i # no special case handling because it's assumed that it has only one solution
-
func twoSum(nums []int, target int) []int { m := map[int]int{} for i := 0; ; i++ { x := nums[i] y := target - x if j, ok := m[y]; ok { return []int{j, i} } m[x] = i } }
-
/** * @param {number[]} nums * @param {number} target * @return {number[]} */ var twoSum = function (nums, target) { const m = new Map(); for (let i = 0; ; ++i) { const x = nums[i]; const y = target - x; if (m.has(y)) { return [m.get(y), i]; } m.set(x, i); } };
-
class Solution { /** * @param Integer[] $nums * @param Integer $target * @return Integer[] */ function twoSum($nums, $target) { $len = count($nums); for ($i = 0; $i < $len; $i++) { for ($j = 1 + $i; $j < $len; $j++) { if ($nums[$i] + $nums[$j] == $target) { return [$i, $j]; } } } } }
-
# @param {Integer[]} nums # @param {Integer} target # @return {Integer[]} def two_sum(nums, target) nums.each_with_index do |x, idx| if nums.include? target - x return [idx, nums.index(target - x)] if nums.index(target - x) != idx end next end end
-
import scala.collection.mutable object Solution { def twoSum(nums: Array[Int], target: Int): Array[Int] = { var map = new mutable.HashMap[Int, Int]() for (i <- 0 to nums.length) { if (map.contains(target - nums(i))) { return Array(map(target - nums(i)), i) } else { map += (nums(i) -> i) } } Array(0, 0) } }
-
public class Solution { public int[] TwoSum(int[] nums, int target) { var m = new Dictionary<int, int>(); for (int i = 0, j; ; ++i) { int x = nums[i]; int y = target - x; if (m.TryGetValue(y, out j)) { return new [] {j, i}; } if (!m.ContainsKey(x)) { m.Add(x, i); } } } }
-
#[ Author: @joe733 ]# import std/enumerate proc twoSum(nums: seq[int], target: int): seq[int] = var bal: int tdx: int for idx, val in enumerate(nums): bal = target - val if bal in nums: tdx = nums.find(bal) if idx != tdx: return @[idx, tdx]
-
use std::collections::HashMap; pub fn soluation(nums: Vec<i32>, target: i32) -> Vec<i32> { let mut map = HashMap::new(); for (i, item) in nums.iter().enumerate() { if map.contains_key(item) { return vec![i as i32, map[item]]; } else { let x = target - nums[i]; map.insert(x, i as i32); } } unreachable!() }
-
class Solution { func twoSum(_ nums: [Int], _ target: Int) -> [Int] { var m = [Int: Int]() var i = 0 while true { let x = nums[i] let y = target - nums[i] if let j = m[target - nums[i]] { return [j, i] } m[nums[i]] = i i += 1 } } }