两数之和

题目描述

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

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

示例

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

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

思路1

一种简单的方法是，使用两层遍历，第一层确定第一个数，然后第二层遍历数组找到和为target的数字。

package com.longhujing.leetcode.t0001;

/**
 * @author longhujing
 * @date 2020-02-01
 */
public class Solution {

    public int[] twoSum(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        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 null;
    }

}

这种解法是很简单也是很容易想到的一种解法，但是整个的执行效率并不高。整个算法的时间复杂度为O(n2)，在LeetCode上面运行测试耗时43ms

思路2

第一种解法的缺陷在于查找耗时太长了，因此如果有一个可以通过一个确切的数值就能够获得对应下标的数据结构就可以节省这一部分的查找时间。在Java中可以考虑使用Map作为这种数据结构，key为确切的数值，value为对应的下标。

package com.longhujing.leetcode.t0001;

import java.util.HashMap;
import java.util.Map;

/**
 * @author longhujing
 * @date 2020-02-01
 */
public class Solution {

    public int[] twoSum(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        Map<Integer, Integer> map = new HashMap<>(nums.length);
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{i, map.get(target - nums[i])};
            }
            map.put(nums[i], i);
        }
        return null;
    }

}

经过改良后，整个算法的时间复杂度为O(n)，LeetCode运行测试耗时2ms

[LeetCode] 两数之和

原文：https://www.cnblogs.com/longhujing/p/12249270.html