摘要:題目解析給出一列整數(shù)數(shù)組和一個數(shù)字,如果計算出數(shù)組中的兩個數(shù)之和等于,那么返回數(shù)組兩個數(shù)的索引。解答基礎(chǔ)的解法應(yīng)該是將數(shù)組遍歷之后取和,如果和等于那么結(jié)束循環(huán)。這種解法的效率為。
題目
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].
給出一列整數(shù)數(shù)組和一個數(shù)字target,如果計算出數(shù)組中的兩個數(shù)之和等于target,那么返回數(shù)組兩個數(shù)的索引。
解答基礎(chǔ)的解法應(yīng)該是將數(shù)組遍歷之后取和,如果和等于target那么結(jié)束循環(huán)。這種解法的效率為O(n^2)。
public int[] twoSum(int[] nums, int target) { int i,j; // 雙層循環(huán)取和 for(i=0;i更高效的解法可以通過將結(jié)果放入HashMap中,通過HashMap的containsKey的方法來查找答案。
相比于O(n)效率的數(shù)組循環(huán),containsKey方法如果在計算hash值能立馬找到key那么效率為O(1),如果找不到key需要繼續(xù)查找鏈表的話,那么效率為O(n),但是又因為HashMap的hash值是分散的,所以查找鏈表的長度相比于數(shù)組循環(huán)的長度是更少的,所以總的來說HashMap的效率是更好的。public static int[] twoSum3(int[] nums , int target){ Mapmap = new HashMap<>(); for(int i =0;i
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/72530.html
摘要:難度就是說給一個整數(shù)數(shù)組如給一個目標數(shù)字如從數(shù)組中找出相加為這個目標數(shù)字的兩個數(shù)的下標就返回的下標只需要給出滿足條件的一對數(shù)字即可這個題想起來比較直接此處給出兩種解法這之后的題目中還有多個數(shù)字相加的相對較難的題目第一種將數(shù)組排序以兩個游標 Two Sum Given an array of integers, return indices of the two numbers suc...
摘要:返回這兩個元素的位置。每個輸入都有且僅有一組滿足條件的元素。想法如果使用蠻力法可以簡單的解決這個問題。但是需要兩層循環(huán),效率低。用來存儲,每一個元素和目標元素的差值和這個元素的位置。因為里的對象也是鍵值對。 題目詳情 Given an array of integers, return indices of the two numbers such that they add up t...
摘要:返回這兩個元素的位置。每個輸入都有且僅有一組滿足條件的元素。想法如果使用蠻力法可以簡單的解決這個問題。但是需要兩層循環(huán),效率低。用來存儲,每一個元素和目標元素的差值和這個元素的位置。因為里的對象也是鍵值對。 題目詳情 Given an array of integers, return indices of the two numbers such that they add up t...
摘要:開坑,以后每周刷一兩道一題目兩數(shù)之和給定一個整數(shù)數(shù)組和一個目標值,請你在該數(shù)組中找出和為目標值的那兩個整數(shù),并返回他們的數(shù)組下標。但是,你不能重復(fù)利用這個數(shù)組中同樣的元素。 開坑,以后每周刷一兩道LeetCode 一、題目 兩數(shù)之和: 給定一個整數(shù)數(shù)組 nums 和一個目標值 target,請你在該數(shù)組中找出和為目標值的那 兩個 整數(shù),并返回他們的數(shù)組下標。你可以假設(shè)每種輸入只會對應(yīng)...
摘要:給定一個整數(shù)數(shù)組和一個目標值,請你在該數(shù)組中找出和為目標值的那兩個整數(shù),并返回他們的數(shù)組下標。示例給定因為所以返回方法,暴力解法。函數(shù)可以將一個數(shù)組轉(zhuǎn)化為一個從開始,值為數(shù)組對應(yīng)元素的字典。 給定一個整數(shù)數(shù)組 nums 和一個目標值 target,請你在該數(shù)組中找出和為目標值的那 兩個 整數(shù),并返回他們的數(shù)組下標。 你可以假設(shè)每種輸入只會對應(yīng)一個答案。但是,你不能重復(fù)利用這個數(shù)組中...
閱讀 977·2021-11-22 09:34
閱讀 2161·2021-11-11 16:54
閱讀 2196·2021-09-27 14:00
閱讀 940·2019-08-30 15:55
閱讀 1525·2019-08-29 12:46
閱讀 599·2019-08-26 18:42
閱讀 639·2019-08-26 13:31
閱讀 3183·2019-08-26 11:52