成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

【LeetCode Easy】001 Two Sum

KevinYan / 1729人閱讀

摘要：兩個(gè)循環(huán)嵌套暴力計(jì)算時(shí)間復(fù)雜度達(dá)到了兩個(gè)指針首尾并行時(shí)間復(fù)雜度這種方法可以滿足這道題的要求，因?yàn)轭}目中明確說(shuō)明了，但是當(dāng)答案不止一個(gè)時(shí)，如為時(shí)，就不能用這種方法了用到循環(huán)遍歷數(shù)組，對(duì)每個(gè)元素計(jì)算和的差，如果該差在中，返回兩個(gè)位置，如果該差不

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:

兩個(gè)for循環(huán)嵌套暴力計(jì)算

時(shí)間復(fù)雜度達(dá)到了O(n2)

兩個(gè)指針首尾并行

時(shí)間復(fù)雜度O(n)

這種方法可以滿足這道題的要求，因?yàn)轭}目中明確說(shuō)明了each input has exactly one solution，但是當(dāng)答案不止一個(gè)時(shí)，如input為[2,2,7,11,15]時(shí)，就不能用這種方法了

Fast Solution：

用到HashMap

for循環(huán)遍歷數(shù)組，對(duì)每個(gè)元素計(jì)算和target的差，如果該差在map中，返回兩個(gè)位置，如果該差不在map中，則將該元素及其位置保存在map中

時(shí)間復(fù)雜度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)形式存儲(chǔ)

無(wú)序

每一次的存取都是通過(guò)計(jì)算一個(gè)hash function獲得這個(gè)key的unique hash值, 這部分是O(1)的，正常情況下使用HashMap的時(shí)間復(fù)雜度就是O(1)，但是如果有collision的話,就是兩個(gè)key算出來(lái)的hash值是一樣的,那就是linear 的complexity, 因?yàn)橐粋€(gè)key里面有兩個(gè)值, 所以worst的情況O(n)

空間復(fù)雜度：每多一對(duì)(key, value)就要分配一個(gè)空間，所以是O(n)

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/74246.html

相關(guān)文章

  • 前端 | 每天一個(gè) LeetCode

    摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語(yǔ)言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...

    張漢慶 評(píng)論0 收藏0

  • leetcode部分題目答案之JavaScript版

    摘要：自己沒(méi)事刷的一些的題目，若有更好的解法，希望能夠一起探討項(xiàng)目地址 自己沒(méi)事刷的一些LeetCode的題目，若有更好的解法，希望能夠一起探討 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...

    alphahans 評(píng)論0 收藏0

  • leetcode-Easy-第1期：two sum

    摘要：原題描述題目意思從數(shù)組中找出返回和在數(shù)組中的位置數(shù)組中一定存在和相加等于，并且和不能相等解法因?yàn)榭隙ㄓ薪?，且值不一樣，所以?shù)組只有兩個(gè)值的時(shí)候這兩個(gè)值就為解判斷對(duì)象是否有一個(gè)為對(duì)象的是原來(lái)數(shù)組的值，是該值的位置其實(shí)思路就是然后返回和對(duì)應(yīng)的 原題描述： Given an array of integers, return indices of the two numbers such t...

    anonymoussf 評(píng)論0 收藏0

  • LeetCode - 001 - 兩數(shù)之和（two-sum）

    摘要：解法返回目錄解題代碼執(zhí)行測(cè)試解題思路使用雙重循環(huán)破解。解法返回目錄解題代碼執(zhí)行測(cè)試知識(shí)點(diǎn)遍歷數(shù)組，返回遍歷項(xiàng)，返回當(dāng)前索引。 Create by jsliang on 2019-05-16 22:19:13 Recently revised in 2019-05-17 14:22:40 Hello 小伙伴們，如果覺(jué)得本文還不錯(cuò)，記得給個(gè) star ， 小伙伴們的 star 是我持續(xù)更新的動(dòng)...

    habren 評(píng)論0 收藏0

  • Leetcode 1: Two Sum 加和

    摘要：難度就是說(shuō)給一個(gè)整數(shù)數(shù)組如給一個(gè)目標(biāo)數(shù)字如從數(shù)組中找出相加為這個(gè)目標(biāo)數(shù)字的兩個(gè)數(shù)的下標(biāo)就返回的下標(biāo)只需要給出滿足條件的一對(duì)數(shù)字即可這個(gè)題想起來(lái)比較直接此處給出兩種解法這之后的題目中還有多個(gè)數(shù)字相加的相對(duì)較難的題目第一種將數(shù)組排序以兩個(gè)游標(biāo) Two Sum Given an array of integers, return indices of the two numbers suc...

    PascalXie 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<