LeetCode001_两数之和

发表于 | 分类于
本文字数： 1.5k | 阅读时长 ≈ 1 分钟

这是一个记录自己LeetCode算法刷题过程的新系列，以方便日后自己的复习，也能为广大网友朋友提供一些方便。
目前LeetCode在国内已经上线了中文版，所以这里我们采用中文版进行记录，这样容易更快理解题干，因为对于解决问题来说，第一步就是充分、正确的理解我们需要做什么。
不过我还是会保留英文的原题作为对照，毕竟多掌握一些英语也是很有好处的事情。

本次要记录的题是LeetCode第001题：两数之和

题干：

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

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]

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

解答：

最初我想到的解答是比较粗暴的双重循环，但是这样是比较低效的，因为他的时间复杂度是O(n^2)，然后经过网友提醒，使用了 哈希表的方式降低了算法复杂度。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 声明结果集
        int[] result = new int[2];
        Map<Integer, Integer> m = new HashMap<>();
        int temp = 0;
        for (int i = 0; i < nums.length; i++) {
            temp = target - nums[i];
            if(m.containsKey(temp)){
                result[0] = m.get(temp);
                result[1] = i;
                break;
            }else{
                m.put(nums[i], i);
            }
        }
        return result;
    }
}

原理分析：

在通常的contains()验证时，我们需要遍历整个list或数组，因此这里的双重for循环每一层循环的算法复杂度都是O(n)，而不一样的是，Map所使用的hash算法是O(1)的时间复杂度，因此我们可以省去本来的内层循环，算法的执行时间也就这样被降低了。

最终成绩：

这里是我跑这个算法的执行结果，仅供大家参考一下：

-c