Leetcode日记–1. Two Sum

发布于 2020-09-14  138 次阅读


懒狗如我,开始在博客中记录每日的LeetCode题解了。希望能坚持下来!

题目如下:

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]
 

Constraints:

2 <= nums.length <= 105
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

我的题解:

我自己写的时候只想到了使用两遍For循环暴力破解的方法 。通过循环把所有数之和求得,便可以得到两数之和等于target的数字组合了。

复杂度分析:

但是这个方法实在是太弱智了。

时间复杂度:O(n^2)
对于每个元素,我们试图通过遍历数组的其余部分来寻找它所对应的目标元素,这将耗费 O(n)O(n) 的时间。因此时间复杂度为 O(n^2)。

空间复杂度:O(1)。

官方大佬题解:

已经知道,target-某一数=另一数,这两个数组成的数对下标即为我们想要的结果。

使用哈希表可以大幅减少查找时间,将时间复杂度降为O(1)。故把每一次target与当前数字的差存在哈希表中,其中key为数字,value为数字在数组中的角标。这样总时间复杂度就被降到了O(n)。

动画演示如上(来自GitHub项目“
LeetCodeAnimation
”)

代码如下:

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

心得感悟:

第一次做LeetCode,确实没想太多操作,使用哈希表空间换时间降低时间复杂度是非常有用的小技(常)巧(常)。

以后继续加油!


你好哇!欢迎来到雷公马碎碎念的地方:)