【LeetCode Easy】001 Two Sum

KevinYan 发布于2019-08-16 16:53 / 1626人阅读

摘要：两个循环嵌套暴力计算时间复杂度达到了两个指针首尾并行时间复杂度这种方法可以满足这道题的要求，因为题目中明确说明了，但是当答案不止一个时，如为时，就不能用这种方法了用到循环遍历数组，对每个元素计算和的差，如果该差在中，返回两个位置，如果该差不

Easy 001 Two Sum Description:

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

My Solution:

两个for循环嵌套暴力计算

时间复杂度达到了O(n²)

两个指针首尾并行

时间复杂度O(n)

这种方法可以满足这道题的要求，因为题目中明确说明了each input has exactly one solution，但是当答案不止一个时，如input为[2,2,7,11,15]时，就不能用这种方法了

Fast Solution：

用到HashMap

for循环遍历数组，对每个元素计算和target的差，如果该差在map中，返回两个位置，如果该差不在map中，则将该元素及其位置保存在map中

时间复杂度O(n)

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

Knowledge

HashMap

以(key, value)形式存储

无序

每一次的存取都是通过计算一个hash function获得这个key的unique hash值, 这部分是O(1)的，正常情况下使用HashMap的时间复杂度就是O(1)，但是如果有collision的话,就是两个key算出来的hash值是一样的,那就是linear 的complexity, 因为一个key里面有两个值, 所以worst的情况O(n)

空间复杂度：每多一对(key, value)就要分配一个空间，所以是O(n)

私有云 GPU服务器 two-sum LeetCode vps001 two

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/74246.html

前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
leetcode部分题目答案之JavaScript版

摘要：自己没事刷的一些的题目，若有更好的解法，希望能够一起探讨项目地址自己没事刷的一些LeetCode的题目，若有更好的解法，希望能够一起探讨 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...

alphahans 2019-08-21 16:20 评论0 收藏0
leetcode-Easy-第1期：two sum

摘要：原题描述题目意思从数组中找出返回和在数组中的位置数组中一定存在和相加等于，并且和不能相等解法因为肯定有解，且值不一样，所以数组只有两个值的时候这两个值就为解判断对象是否有一个为对象的是原来数组的值，是该值的位置其实思路就是然后返回和对应的原题描述： Given an array of integers, return indices of the two numbers such t...

anonymoussf 2019-08-23 15:42 评论0 收藏0
LeetCode - 001 - 两数之和（two-sum）

摘要：解法返回目录解题代码执行测试解题思路使用双重循环破解。解法返回目录解题代码执行测试知识点遍历数组，返回遍历项，返回当前索引。 Create by jsliang on 2019-05-16 22:19:13 Recently revised in 2019-05-17 14:22:40 Hello 小伙伴们，如果觉得本文还不错，记得给个 star ，小伙伴们的 star 是我持续更新的动...

habren 2019-05-23 17:27 评论0 收藏0
Leetcode 1: Two Sum 加和

摘要：难度就是说给一个整数数组如给一个目标数字如从数组中找出相加为这个目标数字的两个数的下标就返回的下标只需要给出满足条件的一对数字即可这个题想起来比较直接此处给出两种解法这之后的题目中还有多个数字相加的相对较难的题目第一种将数组排序以两个游标 Two Sum Given an array of integers, return indices of the two numbers suc...

PascalXie 2019-08-14 17:01 评论0 收藏0