1. Two Sum
題目敘述
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 <= 10**4-10**9 <= nums[i] <= 10**9-10**9 <= target <= 10**9- Only one valid answer exists.
Follow-up: Can you come up with an algorithm that is less than O(n**2) time complexity?
Hint 1:
A really brute force way would be to search for all possible pairs of numbers but that would be too slow. Again, it's best to try out brute force solutions for just for completeness. It is from these brute force solutions that you can come up with optimizations.
Hint 2:
So, if we fix one of the numbers, say x, we have to scan the entire array to find the next number y which is value - x where value is the input parameter. Can we change our array somehow so that this search becomes faster?
Hint 3:
The second train of thought is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?
題目翻譯
解法解析
官方提供了三種解法：暴力破解、兩次遍歷 Hash Table、一次遍歷 Hash Table 其中最後的兩種方式，空間複雜度和時間複雜度相同。 這邊採用的是 One-pass Hash Table 的解法，因為覺得只使用一次遍歷的解法比較簡潔
這邊以 JavaScript 做範例
- 先建立一個 Hash Table
- 使用迴圈將參數
nums做遍歷 - 在每一次的遍歷中，將
nums中的元素和target做相減得到diff - 如果在 Hash Table 中不存在則存入其中，如果已經存在則回傳
而在 Memory 更優化的方式，是不另外使用 Hash Table 來做儲存，直接將 diff 在 nums 做查找。因為有些程式語言沒有支援類似 indexOf() 的語法糖，所以會用第二層回圈做判斷
第一步，先使用 for 迴圈去遍歷傳入的 nums 陣列。
第二步，將 target 減去每次 nums 遍歷的值 diff， diff 就是我們希望在陣列 nums 中找到的另一個配對的值。
第三步，將 diff放到 map 中判斷，是否已經存在，如果不存在就暫存此次遍歷的值和其 index 到 map 中。如果找到了就將找到的兩個 index 放在陣列回傳
解法範例
Go
Runtime
func twoSum(nums []int, target int) []int {
hash := make(map[int]int)
for i, num := range nums {
if j, ok := hash[target-num]; ok {
return []int{j, i}
}
hash[num] = i
}
return []int{}
}
Memory
func twoSum(nums []int, target int) []int {
n := len(nums)
for i := 0; i < n-1; i++ {
for j := i + 1; j < n; j++ {
if nums[i]+nums[j] == target {
return []int{i, j}
}
}
}
return []int{}
}
JavaScript
Runtime
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var 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 [i, map.get(diff)];
map.set(nums[i], i);
}
};
Memory
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
for (let i = 0; i < nums.length; i++) {
const diff = target - nums[i];
if (nums.includes(diff) && i !== nums.indexOf(diff)) {
return [nums.indexOf(diff), i];
}
}
};
Kotlin
Runtime
class Solution {
fun twoSum(nums: IntArray, target: Int): IntArray {
val hash = mutableMapOf<Int, Int>()
for ((index, num) in nums.withIndex()) {
var diff = target - num
if (hash.containsKey(diff)) {
return intArrayOf(hash.getValue(diff), index)
}
hash[num] = index
}
return intArrayOf()
}
}
Memory
class Solution {
fun twoSum(nums: IntArray, target: Int): IntArray {
for ((index, num) in nums.withIndex()) {
var diff = target - num
if (nums.contains(diff) && nums.indexOf(diff) != index) {
return intArrayOf(nums.indexOf(diff), index)
}
}
return intArrayOf()
}
}
PHP
Runtime
class Solution
{
/**
* @param Integer[] $nums
* @param Integer $target
* @return Integer[]
*/
function twoSum($nums, $target)
{
$map = [];
$size = count($nums);
for ($i = 0; $i < $size; $i++) {
$complement = $target - $nums[$i];
if (array_key_exists($complement, $map)) {
return [$i, $map[$complement]];
}
$map[$nums[$i]] = $i;
}
}
}
Memory
class Solution
{
/**
* @param Integer[] $nums
* @param Integer $target
* @return Integer[]
*/
function twoSum($nums, $target)
{
for ($i = 0; $i < sizeof($nums); $i++) {
for ($j = $i + 1; $j < sizeof($nums); $j++) {
if ($nums[$i] + $nums[$j] === $target) {
return [$i, $j];
}
}
}
}
}
Python
Runtime
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashmap = {}
for i in range(len(nums)):
complement = target - nums[i]
if complement in hashmap:
return [i, hashmap[complement]]
hashmap[nums[i]] = i
Memory
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
diff = target - nums[i]
if diff in nums and i is not nums.index(diff):
return [i, nums.index(diff)]
Rust
Runtime
use std::collections::HashMap;
impl Solution {
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut hash_map = HashMap::with_capacity(nums.len());
for (idx, &num) in nums.iter().enumerate() {
let complement = target - num;
if let Some(&find_target) = hash_map.get(&complement) {
return vec![find_target as i32, idx as i32];
}
hash_map.insert(num, idx);
}
vec![]
}
}
Memory
impl Solution {
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
if nums.len() == 2 {
return vec![0, 1];
}
for (i, x) in nums.iter().enumerate() {
for (j, y) in nums.iter().enumerate().filter(|(j, _)| *j != i) {
if x + y == target {
return vec![i as i32, j as i32];
}
}
}
vec![]
}
}
Swift
Runtime
class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var hash: [Int : Int] = [:]
for (i, num) in nums.enumerated() {
if let index = hash[target - num] {
return [index, i]
}
hash[num] = i
}
return []
}
}
Memory
class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
for i in 0..<nums.count {
for j in (i + 1)..<nums.count {
var sum = nums[i] + nums[j]
if (sum == target) {
return [i, j]
}
}
}
return []
}
}