1. Two Sum

2018-06-20  本文已影响0人  JamesLivin

Problem

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].

给定一个整数数组,当两个数相加等于目标值时,返回其下表。
你可以假设每一组输入都仅有一个确切的结果,你不可以使用同样的元素两次。

Solution

Brute Force/暴力破解

遍历每一个元素x,并且寻找另一个元素y,使得y = target - x。

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[j] == target - nums[i]) {
                return new int[] { i, j };
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

复杂度分析

Tow-pass Hash Table/二次遍历散列表

为了改进时间复杂度,我们需要一种更有效的方式来检查数组中是否存在对应的元素。如果对应元素存在,我们需要查询它的下标。我们可以通过Hash表来存储每一个元素的下标。
我们使用hash表来将查询的时间复杂度从O(n)降到O(1)。hash表的查询时间近似于一个常量,但是当碰撞发生时,一次查询可能需要O(n)的时间。当hash方法选择得当时,一次查询的时间仅需要O(1)。
一个简单的实现就是使用二次遍历。在第一次遍历时,我们将每一个元素的值和下标添加到hash表中。然后,在第二次遍历时,我们查询每个元素的对应值是否存在(target - nums[i])。注意对应值不能是nums[i]自身。

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement) && map.get(complement) != i) {
            return new int[] { i, map.get(complement) };
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

复杂度分析

One-pass Hash Table/一次遍历散列表

我们可以使用一次遍历来实现。当我们遍历并且插入元素的时候,我们同时回看并且复查是否有对应的元素已经存在于散列表中。如果存在我们就得到了一个解,并且立刻返回结果。

public int[] twoSum(int[] nums, int target) {
    Map<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);
    }
    throw new IllegalArgumentException("No two sum solution");
}

复杂度分析

上一篇 下一篇

猜你喜欢

热点阅读