LeetCode 1：两数之和 Two Sum

爱写bug

发布于 2019-10-15 15:39:06

3980

发布于 2019-10-15 15:39:06

文章被收录于专栏：爱写Bug爱写Bug

题目：

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

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.

示例:

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

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

解题思路：

暴力穷举：外循环遍历每个元素 x，内循环查找是否存在一个值与 target - x 相等的目标元素，返回相等的目标元素和 x 的索引。时间复杂度 O (n^2)，效率太低，pass。
哈希表：哈希映射（map、dict），key 保存该元素，value 保存该元素索引。
- 两次遍历法：第一次遍历把所有元素及其索引保存到哈希映射，第二次遍历查找 target - x 相等的目标元素
- 一次遍历法：假如 y = target - x，则 x = target -y，所以一次遍历在存入哈希映射的同时查找是否存在一个值与 target - x 相等的目标元素。例：nums = [2, 11, 7, 15], target = 9, hashmap = { } 遍历： i = 0: target - x = 9 - 2 = 7, 7 不存在于 hashmap 中，则 x(2) 加入 hashmap, hashmap = {2 : 0} i = 1: target - x = 9 - 11 = -2, -2 不存在于 hashmap 中，则 x(-2) 加入 hashmap, hashmap = {2 : 0, 11 : 1} i = 2: target - x = 9 - 7 = 2, 2 存在于 hashmap 中，则返回列表 [2, 0]

代码：

两次遍历（Java）：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {//一次遍历转换成键值对，key为元素值，value为索引值
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {//二次遍历查找符合条件的元素
            int res = target - nums[i];
            if (map.containsKey(res) && map.get(res) != i) {//查找到的目标元素不能为其本身
                return new int[]{i, map.get(res)};
            }
        }
        return null;
    }
}

一次遍历 (Java)：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int res = target - nums[i];
            if (map.containsKey(res)) {//因为自身元素还未加入到 hashmap，无需 map.get(res) != i 条件判断
                return new int[]{i, map.get(res)};
            }
            map.put(nums[i], i);//未找到目标元素则将其加入 hashmap
        }
        return null;
    }
}

一次遍历 (Python)：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic = {}
        for i, num in enumerate(nums): #枚举 nums 数组
            if num in dic:
                return [dic[num], i]
            else:
                dic[target-num] = i

利用 Python 数组自带 index 方法解题：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i, num in enumerate(nums):
            if target-num in nums and nums.index(target-num) != i:
                return [i, nums.index(target-num)]