1.两数之和(Two Sum)E

英文题目

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

中文题目

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

暴力解法

直接枚举数组中的每一个数 num，寻找数组中 num 后面的元素是否存在 target-num
时间复杂度O(n^2)，空间复杂度O(1)

# python: 时间 2668 ms, 击败 33.69%; 内存 16.8 MB, 击败 36.80%
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i+1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []

// C++: 时间 304 ms, 击败 24.16%; 内存 10 MB, 击败 63.62%
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); ++i) {
            for (int j = i+1; j < nums.size(); ++j) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        return {};
    }
};

// java: 时间 54 ms, 击败 26.90%; 内存 42.6 MB, 击败 28.40%
class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; ++i) {
            for (int j = i+1; j < nums.length; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}

// go: 时间 20 ms, 击败 27.87%; 内存 3.5 MB, 击败 99.24%
func twoSum(nums []int, target int) []int {
    for i, _ := range nums {
        for j := i+1; j < len(nums); j++ { // 注意go没有++j的写法
            if nums[i] + nums[j] == target {
                return []int{i, j}
            }
        }
        // 注意，下面不能这样用range，因为会重置j的索引
        // 如i=1时，nums[2]的对应索引 j=0
        // for j, _ := range nums[i+1:] {
        //     if nums[i] + nums[j] == target {
        //         return []int{i, j}
        //     }
        // }
    }
    return []int{}
}

// rust: 时间 28 ms, 击败 23.92%; 内存 2.16 MB, 击败 78.25%
impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        for i in 0..nums.len() {
            for j in i+1..nums.len() {
                if nums[i] + nums[j] == target {
                    return vec![i as i32, j as i32];
                }
            }
        }
        vec![]
    }
}

// javascript: 时间 112 ms, 击败 27.51%; 内存 41.4 MB, 击败 68.65%
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    for (let i = 0; i < nums.length; ++i) {
        for (let j = i+1; j < nums.length; ++j) {
            if (nums[i] + nums[j] == target) {
                return [i, j];
            }
        }
    }
    return [];
};

// typescript: 时间 128 ms, 击败 16.08%; 内存 50.87 MB, 击败 9.04%
function twoSum(nums: number[], target: number): number[] {
    for (let i = 0; i < nums.length; ++i) {
        for (let j = i+1; j < nums.length; ++j) {
            if (nums[i] + nums[j] == target) {
                return [i, j];
            }
        }
    }
    return [];
};

// scala: 时间 580 ms, 击败 46.58%; 内存 55.56 MB, 击败 46.57%
object Solution {
    def twoSum(nums: Array[Int], target: Int): Array[Int] = {
        for (i <- nums.indices; j <- i + 1 until nums.length) {
            if (nums(i) + nums(j) == target) {
                return Array(i, j)
            }
        }
        Array()
    }
}

一次哈希

使用哈希表，对每一个 num，先查询哈希表中是否存在 target - num，若存在，返回结果，若不存在，将 key=num,value=index 插入哈希表中
时间复杂度O(n)，空间复杂度O(n)，这里n是哈希表的开销

# python: 时间 40 ms, 击败 86.10%; 内存 17.5 MB, 击败 5.11%
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        numDict = {}
        for i, num in enumerate(nums):
            if target - num in numDict:
                return [i, numDict[target - num]]
            numDict[num] = i
        return []

// C++: 时间 4 ms, 击败 99.31%; 内存 10.6 MB, 击败 26.78%
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> numDict;
        for (int i = 0; i < nums.size(); ++i) {
            auto mit = numDict.find(target - nums[i]);
            if (mit != numDict.end()) {
                return {i, mit->second};
            }
            numDict[nums[i]] = i;
        }
        return {};
    }
};

// java: 时间 1 ms, 击败 98.17%; 内存 42.2 MB, 击败 47.86%
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> numDict = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
            if (numDict.containsKey(target - nums[i])) {
                return new int[]{i, numDict.get(target - nums[i])};
            }
            numDict.put(nums[i], i);
        }
        return new int[0];
    }
}

// go: 时间 4 ms, 击败 95.47%; 内存 4.1 MB, 击败 44.28%
func twoSum(nums []int, target int) []int {
    numDict := map[int]int{}
    for i, num := range nums {
        if j, ok := numDict[target - num]; ok {
            return []int{i, j}
        }
        numDict[num] = i
    }
    return []int{}
}

// rust: 时间 0 ms, 击败 100%; 内存 2.15 MB, 击败 78.59%
use std::collections::HashMap;

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut numDict = HashMap::with_capacity(nums.len());
        for (i, &num) in nums.iter().enumerate() {
            if let Some(&j) = numDict.get(&(target - num)) {
                return vec![i as i32, j];
            }
            numDict.insert(num, i as i32);
        }
        vec![]
    }
}

// javascript: 时间 72 ms, 击败 60.99%; 内存 42.2 MB, 击败 36.23%
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const numDict = new Map();
    for (let i = 0; i < nums.length; ++i) {
        if (numDict.has(target - nums[i])) {
            return [i, numDict.get(target - nums[i])];
        }
        numDict.set(nums[i], i);
    }
    return [];
};

// typescript: 时间 100 ms, 击败 31.45%; 内存 51.14 MB, 击败 7.86%
function twoSum(nums: number[], target: number): number[] {
    const numDict: Record<number, number> = {};
    for (let i = 0; i < nums.length; ++i) {
        if (target - nums[i] in numDict) {
            return [i, numDict[target - nums[i]]];
        }
        numDict[nums[i]] = i;
    }
    return [];
};

// scala: 时间 512 ms, 击败 97.26%; 内存 55.53 MB, 击败 50.86%
object Solution {
    def twoSum(nums: Array[Int], target: Int): Array[Int] = {
        val numDict = scala.collection.mutable.Map[Int, Int]()
        for (i <- nums.indices) {
            val num = nums(i)
            numDict.get(target - num) match {
                case Some(j) => return Array(j, i)
                case None => numDict(num) = i
            }
        }
        Array()
    }
}

# 1.两数之和(Two Sum)E

# 英文题目

# 中文题目

# 暴力解法

# 一次哈希

1.两数之和(Two Sum)E

英文题目

中文题目

暴力解法

一次哈希