【LeetCode Easy】001 Two Sum

KevinYan 發布于2019-08-16 16:53 / 1705人閱讀

摘要：兩個循環嵌套暴力計算時間復雜度達到了兩個指針首尾并行時間復雜度這種方法可以滿足這道題的要求，因為題目中明確說明了，但是當答案不止一個時，如為時，就不能用這種方法了用到循環遍歷數組，對每個元素計算和的差，如果該差在中，返回兩個位置，如果該差不

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(n2)

兩個指針首尾并行

時間復雜度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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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