力扣00001.两数之和

发表于 分类于 阅读次数： 本文字数： 1.7k 阅读时长 ≈ 6 分钟
两数之和、数组、哈希表、简单

题目描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

  • $2 <= nums.length <= 10^4$
  • $-10^9 <= nums[i] <= 10^9$
  • $-10^9 <= target <= 10^9$

只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 $O(n^2)$ 的算法吗？

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash_map;
        for (int i = 0; i < nums.size(); ++i) {
            int complement = target - nums[i];
            if (hash_map.find(complement) != hash_map.end()) {
                return {hash_map[complement], i};
            }
            hash_map[nums[i]] = i;
        }
        return {};
    }
};

结果

执行用时 : 12 ms, 击败 70.06% 使用 C++ 的用户

内存消耗 : 10.2 MB, 击败 0.82% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<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 new int[]{};
    }
}

结果

执行用时 : 1 ms, 击败 99.50% 使用 Java 的用户

内存消耗 : 43.02 MB, 击败 5.10% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        num_indices = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in num_indices:
                return [num_indices[complement], i]
            num_indices[num] = i
        return []

结果

执行用时 : 24 ms, 击败 78.55% 使用 Python 的用户

内存消耗 : 13.66 MB, 击败 65.80% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_indices = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in num_indices:
                return [num_indices[complement], i]
            num_indices[num] = i
        return []

结果

执行用时 : 40 ms, 击败 92.95% 使用 Python3 的用户

内存消耗 : 17.39 MB, 击败 13.79% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int* result = (int*)malloc(2 * sizeof(int));
    *returnSize = 0;
    for (int i = 0; i < numsSize - 1; i++) {
        for (int j = i + 1; j < numsSize; j++) {
            if (nums[i] + nums[j] == target) {
                result[0] = i;
                result[1] = j;
                *returnSize = 2;
                return result;
            }
        }
    }
    free(result);
    return NULL;
}

结果

执行用时 : 120 ms, 击败 67.82% 使用 C 的用户

内存消耗 : 6.93 MB, 击败 49.60% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        Dictionary<int, int> numIndices = new Dictionary<int, int>();
        for (int i = 0; i < nums.Length; i++) {
            int complement = target - nums[i];
            if (numIndices.ContainsKey(complement)) {
                return new int[]{numIndices[complement], i};
            }
            numIndices[nums[i]] = i;
        }
        return new int[]{};
    }
}

结果

执行用时 : 140 ms, 击败 73.82% 使用 C# 的用户

内存消耗 : 43.81 MB, 击败 32.02% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const numIndices = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (numIndices.has(complement)) {
            return [numIndices.get(complement), i];
        }
        numIndices.set(nums[i], i);
    }
    return [];
};

结果

执行用时 : 68 ms, 击败 71.65% 使用 JavaScript 的用户

内存消耗 : 42.16 MB, 击败 40.42% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
function twoSum(nums: number[], target: number): number[] {
    const numIndices: Map<number, number> = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement: number = target - nums[i];
        if (numIndices.has(complement)) {
            return [numIndices.get(complement)!, i];
        }
        numIndices.set(nums[i], i);
    }
    return [];
}

结果

执行用时 : 72 ms, 击败 68.51% 使用 TypeScript 的用户

内存消耗 : 44.71 MB, 击败 30.74% 使用 TypeScript 的用户

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($nums, $target) {
        $numIndices = array();
        foreach ($nums as $index => $num) {
            $complement = $target - $num;
            if (array_key_exists($complement, $numIndices)) {
                return array($numIndices[$complement], $index);
            }
            $numIndices[$num] = $index;
        }
        return array();
    }
}

结果

执行用时 : 8 ms, 击败 99.66% 使用 PHP 的用户

内存消耗 : 20.01 MB, 击败 7.01% 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var numIndices = [Int: Int]()
        for (index, num) in nums.enumerated() {
            let complement = target - num
            if let complementIndex = numIndices[complement] {
                return [complementIndex, index]
            }
            numIndices[num] = index
        }
        return []
    }
}

结果

执行用时 : 36 ms, 击败 93.84% 使用 Swift 的用户

内存消耗 : 14.39 MB, 击败 7.81% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val numIndices = HashMap<Int, Int>()
        for (i in nums.indices) {
            val complement = target - nums[i]
            if (numIndices.containsKey(complement)) {
                return intArrayOf(numIndices[complement]!!, i)
            }
            numIndices[nums[i]] = i
        }
        return intArrayOf()
    }
}

结果

执行用时 : 204 ms, 击败 66.38% 使用 Kotlin 的用户

内存消耗 : 37.57 MB, 击败 63.17% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    List<int> twoSum(List<int> nums, int target) {
    Map<int, int> numIndices = {};
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (numIndices.containsKey(complement)) {
        return [numIndices[complement]!, i];
        }
        numIndices[nums[i]] = i;
    }
    return [];
    }
}

结果

执行用时 : 256 ms, 击败 100.00% 使用 Dart 的用户

内存消耗 : 155.91 MB, 击败 20.20% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
func twoSum(nums []int, target int) []int {
    numIndices := make(map[int]int)
    for i, num := range nums {
        complement := target - num
        if idx, ok := numIndices[complement]; ok {
            return []int{idx, i}
        }
        numIndices[num] = i
    }
    return []int{}
}

结果

执行用时 : 4 ms, 击败 94.26% 使用 Go 的用户

内存消耗 : 4.02 MB, 击败 63.86% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}
def two_sum(nums, target)
    num_indices = {}
    nums.each_with_index do |num, index|
        complement = target - num
        if num_indices.key?(complement)
            return [num_indices[complement], index]
        end
        num_indices[num] = index
    end
    return []
end

结果

执行用时 : 68 ms, 击败 75.61% 使用 Ruby 的用户

内存消耗 : 207.09 MB, 击败 41.46% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
object Solution {
  def twoSum(nums: Array[Int], target: Int): Array[Int] = {
    var numIndices = Map.empty[Int, Int]
    for ((num, index) <- nums.zipWithIndex) {
      val complement = target - num
      if (numIndices.contains(complement)) {
        return Array(numIndices(complement), index)
      }
      numIndices += (num -> index)
    }
    Array.empty[Int]
  }
}

结果

执行用时 : 564 ms, 击败 58.23% 使用 Scala 的用户

内存消耗 : 55.63 MB, 击败 29.12% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
use std::collections::HashMap;

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

结果

执行用时 : 0 ms, 击败 100.00% 使用 Rust 的用户

内存消耗 : 2.44 MB, 击败 29.41% 使用 Rust 的用户

Racket

1
2
3
4
5
6
7
8
9
10
11
(define (two-sum nums target)
  (define (find-indexes nums index seen)
    (cond
      ((null? nums) '())
      ((hash-has-key? seen (- target (car nums)))
       (list (hash-ref seen (- target (car nums))) index))
      (else
       (hash-set! seen (car nums) index)
       (find-indexes (cdr nums) (+ index 1) seen))))
  (find-indexes nums 0 (make-hash))
)

结果

执行用时 : 280 ms, 击败 42.86% 使用 Racket 的用户

内存消耗 : 124.89 MB, 击败 14.29% 使用 Racket 的用户

Erlang

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
-spec two_sum(Nums :: [integer()], Target :: integer()) -> [integer()].
two_sum(Nums, Target) ->
    lists:reverse(get_indices(Nums, Target, 0, length(Nums), #{})).
get_indices(_, _, _, 0, _) ->
    [];
get_indices(Nums, Target, Index1, Index2, Seen) ->
    Head = hd(Nums),
    RestNums = tl(Nums),
    case maps:is_key(Target - Head, Seen) of
        true ->
            [maps:get(Target - Head, Seen), Index1];
        false ->
            NewSeen = maps:put(Head, Index1, Seen),
            get_indices(RestNums, Target, Index1 + 1, Index2 - 1, NewSeen)
    end.

结果

执行用时 : 216 ms, 击败 81.25% 使用 Erlang 的用户

内存消耗 : 48.04 MB, 击败 50.00% 使用 Erlang 的用户

Elixir

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
defmodule Solution do
  @spec two_sum(nums :: [integer], target :: integer) :: [integer]
  def two_sum(nums, target) do
    two_sum_helper(nums, target, 0, %{})
  end
  defp two_sum_helper([], _, _, _), do: []
  defp two_sum_helper([num | rest], target, index, seen) do
    complement = target - num
    case Map.get(seen, complement) do
      nil ->
        two_sum_helper(rest, target, index + 1, Map.put(seen, num, index))
      comp_index ->
        [comp_index, index]
    end
  end
end

结果

执行用时 : 272 ms, 击败 77.78% 使用 Elixir 的用户

内存消耗 : 61.56 MB, 击败 11.11% 使用 Elixir 的用户