美文网首页
1、Two Sum(两数之和)

1、Two Sum(两数之和)

作者: 古月大月半 | 来源:发表于2018-08-13 09:13 被阅读0次

题目

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.

举例

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

思路一:暴力求解

这是最容易想到的思路,也最好实现。使用双重循环,相当于是列举出所有可能出现的两个数相加的组合,只要出现符合条件的两个数,则直接返回相关的索引。

java代码:

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");
}

复杂度分析:

  1. 时间复杂度:O(n^2)
  2. 空间复杂度:O(1)

思路二:使用hashMap求解

很显然的,暴力解法并不优雅。有一些环节是可以使用更加高效的方式来完成的。比如,寻找【target−nums[i]】。要查找一个集合中是否存在某一个元素。在java中使用hashMap比较高效。
使用hashtable之后,我们相比于暴力解法,相当于将第二层循环的任务交给了hashMap来完成。这就将第二层循环O(n)的复杂度降低为O(1)。当然,考虑hashMap中元素的碰撞,有可能也会退化为O(n)。不过如果小心选取hash函数,通常对于这个解法都可以提高效率。
最重要的一点,就是hashMap的设计,我们如何设计hashMap的key和value也非常关键。在这里,我们将数组的数据值作为key,将数据值对应的索引作为value。这样就能充分利用hashMap的相关API来完成我们需要的功能。

java代码:

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");
}

复杂度分析:

  1. 时间复杂度:O(n)
  2. 空间复杂度:O(n)

思路三:在思路二的基础上进一步改进

思路二中,我们使用了两个单独循环。第一个循环用于构建hashMap,第二个循环用于完成题目需求。实际上可以将第一个循环所做的工作放到第二个循环中。

java代码:

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");
}

复杂度分析:

和思路二相同

我的思考:

三种思路(严格来说是两种),实际上很好的体现了空间换时间的一个基本原理。使用空间来记录一些必要的信息,可以免除不必要的循环操作。这个在算法中非常常用。
另外,转化思维在这个题目中有很好的体现,我们将计算两个数的和等于目标值,转换为了寻找目标值与其中一个数的差值,方便我们更好的设计算法。

相关文章

网友评论

      本文标题:1、Two Sum(两数之和)

      本文链接:https://www.haomeiwen.com/subject/hrlybftx.html