Skip to content

Latest commit

 

History

History
194 lines (146 loc) · 4.7 KB

19.two-sum.md

File metadata and controls

194 lines (146 loc) · 4.7 KB
Raw

1. 两数之和

https://leetcode-cn.com/problems/two-sum

题目描述

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。



示例:

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法 1：哈希表

思路

在遍历数组的同时把数字和下标存进哈希表中，然后看 目标值 - 当前数字 是否存在于哈希表中，有的话直接返回结果，没有就继续遍历。

由于不能使用同一个元素，要注意先检查，再将当前数字加入哈希表。

复杂度分析

  • 时间复杂度：$O(N)$，N 为数组长度，最坏的情况下数组中的每个元素都被访问一次，访问数组元素的时间是 $O(1)$，哈希表插入和查询元素的时间也是 $O(1)$。
  • 空间复杂度：$O(N)$，N 为数组长度，用来存元素和下标的哈希表所需的空间。

代码(JavaScript/Python/C++)

JavaScript Code

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
    if (!nums || !nums.length) return [];

    const map = {};
    for (let i = 0; i < nums.length; i++) {
        const num = nums[i];
        const diff = target - num;

        if (diff in map) return [map[diff], i];
        map[num] = i;
    }
};

Python Code

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        hashmap = {}
        for i, n in enumerate(nums):
            diff = target - n
            if diff in hashmap:
                return [hashmap[diff], i]
            hashmap[n] = i

C++ Code

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> seen;
        for (int i = 0; i < nums.size(); i++) {
            int sub = target - nums[i];
            auto it = seen.find(sub);
            if (it != seen.end()) {
                return {it->second, i};
            }
            seen[nums[i]] = i;
        }
        return {};
    }
};

方法 2：排序+双指针

思路

  • 先给数组排序，再用双指针查找。
  • 不过题目要求返回下标，所以排序之前还需要保存原本的下标。

复杂度分析

  • 时间复杂度：$O(NlogN)$，N 为数组长度。
  • 空间复杂度：$O(N)$。

代码

JavaScript Code

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
    if (!nums || !nums.length) return [];

    // 保存原来的下标，然后升序排序，nums 中元素的格式是 [num, index]
    // [2,7,11,15] => [[2, 0], [7, 1], [11, 2], [15, 3]]
    nums = nums.map((n, i) => [n, i]);
    nums.sort((a, b) => a[0] - b[0]);

    let l = 0,
        r = nums.length - 1;
    while (l < r) {
        const n1 = nums[l][0],
            n2 = nums[r][0];

        if (n1 + n2 === target) return [nums[l][1], nums[r][1]];

        // 太大了，右指针左移
        if (n1 + n2 > target) r--;
        // 太小了，左指针右移
        else l++;
    }
};

方法 3：暴力法

思路

暴力法也顺便做一下吧。

复杂度分析

  • 时间复杂度：$O(N^2)$，N 为数组长度。
  • 空间复杂度：$O(1)$。

代码

JavaScript Code

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
    if (!nums || !nums.length) return [];

    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];
        }
    }
};

更多题解可以访问：https://github.com/suukii/91-days-algorithm