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.
Examples:
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]Solution in Python:
To solve this problem efficiently, we can use a hash map (or dictionary) to keep track of the indices of the elements we have seen so far. This allows us to check in constant time whether the complement of the current element (i.e., target - nums[i]) exists in the array. Here is the implementation in Python with detailed comments:
Python
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
# Dictionary to store the value and its corresponding index
num_to_index = {}
# Iterate over the list of numbers
for i, num in enumerate(nums):
# Calculate the complement of the current number
complement = target - num
# Check if the complement is already in the dictionary
if complement in num_to_index:
# If it is, we have found the solution, return the indices
return [num_to_index[complement], i]
# Otherwise, add the current number and its index to the dictionary
num_to_index[num] = i
# In case no solution is found (though the problem guarantees one solution exists)
return []
# Example usage:
# solution = Solution()
# print(solution.twoSum([2, 7, 11, 15], 9)) # Output: [0, 1]
# print(solution.twoSum([3, 2, 4], 6)) # Output: [1, 2]
# print(solution.twoSum([3, 3], 6)) # Output: [0, 1]
Explanation:
- Dictionary Initialization: We initialize an empty dictionary
num_to_indexto store each number from the array along with its index. - Iteration: We iterate through the list using
enumeratewhich provides both the indexiand the valuenumat each iteration. - Complement Calculation: For each element
num, we calculate its complement astarget - num. - Complement Check: We check if this complement is already present in the dictionary
num_to_index. If it is, it means that the current numbernumand the complement add up to the target. We return their indices. - Dictionary Update: If the complement is not found, we store the current number along with its index in the dictionary.
- Return Result: If we find the solution during the iteration, we return the indices immediately. Given the problem’s guarantee, there will always be exactly one solution.
This approach ensures that we solve the problem in linear time O(n), as we only traverse the list once, and dictionary operations (insertion and lookup) are average constant time O(1).
Solution in Javascript:
JavaScript
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
// Create an object to store the value and its corresponding index
let numToIndex = {};
// Iterate over the list of numbers
for (let i = 0; i < nums.length; i++) {
let num = nums[i];
// Calculate the complement of the current number
let complement = target - num;
// Check if the complement is already in the object
if (complement in numToIndex) {
// If it is, we have found the solution, return the indices
return [numToIndex[complement], i];
}
// Otherwise, add the current number and its index to the object
numToIndex[num] = i;
}
// In case no solution is found (though the problem guarantees one solution exists)
return [];
};
// Example usage:
console.log(twoSum([2, 7, 11, 15], 9)); // Output: [0, 1]
console.log(twoSum([3, 2, 4], 6)); // Output: [1, 2]
console.log(twoSum([3, 3], 6)); // Output: [0, 1]
Solution in Java:
Java
import java.util.HashMap;
class Solution {
public int[] twoSum(int[] nums, int target) {
// Create a HashMap to store the value and its corresponding index
HashMap<Integer, Integer> numToIndex = new HashMap<>();
// Iterate over the array of numbers
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
// Calculate the complement of the current number
int complement = target - num;
// Check if the complement is already in the HashMap
if (numToIndex.containsKey(complement)) {
// If it is, we have found the solution, return the indices
return new int[] { numToIndex.get(complement), i };
}
// Otherwise, add the current number and its index to the HashMap
numToIndex.put(num, i);
}
// In case no solution is found (though the problem guarantees one solution exists)
return new int[] {};
}
// Example usage:
public static void main(String[] args) {
Solution solution = new Solution();
int[] result1 = solution.twoSum(new int[] { 2, 7, 11, 15 }, 9);
System.out.println("Indices: [" + result1[0] + ", " + result1[1] + "]"); // Output: [0, 1]
int[] result2 = solution.twoSum(new int[] { 3, 2, 4 }, 6);
System.out.println("Indices: [" + result2[0] + ", " + result2[1] + "]"); // Output: [1, 2]
int[] result3 = solution.twoSum(new int[] { 3, 3 }, 6);
System.out.println("Indices: [" + result3[0] + ", " + result3[1] + "]"); // Output: [0, 1]
}
}
Solution in C#:
C#
using System;
using System.Collections.Generic;
public class Solution {
public int[] TwoSum(int[] nums, int target) {
// Create a dictionary to store the value and its corresponding index
Dictionary<int, int> numToIndex = new Dictionary<int, int>();
// Iterate over the array of numbers
for (int i = 0; i < nums.Length; i++) {
int num = nums[i];
// Calculate the complement of the current number
int complement = target - num;
// Check if the complement is already in the dictionary
if (numToIndex.ContainsKey(complement)) {
// If it is, we have found the solution, return the indices
return new int[] { numToIndex[complement], i };
}
// Otherwise, add the current number and its index to the dictionary
numToIndex[num] = i;
}
// In case no solution is found (though the problem guarantees one solution exists)
return new int[] {};
}
}