LeetCode-1 Two Sum

Dr_Noooo 發(fā)布于2019-08-16 13:54 / 2214人閱讀

摘要：題目解析給出一列整數(shù)數(shù)組和一個(gè)數(shù)字，如果計(jì)算出數(shù)組中的兩個(gè)數(shù)之和等于，那么返回?cái)?shù)組兩個(gè)數(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ù)組和一個(gè)數(shù)字target，如果計(jì)算出數(shù)組中的兩個(gè)數(shù)之和等于target，那么返回?cái)?shù)組兩個(gè)數(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
更高效的解法可以通過(guò)將結(jié)果放入HashMap中，通過(guò)HashMap的containsKey的方法來(lái)查找答案。
相比于O(n)效率的數(shù)組循環(huán)，containsKey方法如果在計(jì)算hash值能立馬找到key那么效率為O(1)，如果找不到key需要繼續(xù)查找鏈表的話，那么效率為O(n)，但是又因?yàn)镠ashMap的hash值是分散的，所以查找鏈表的長(zhǎng)度相比于數(shù)組循環(huán)的長(zhǎng)度是更少的，所以總的來(lái)說(shuō)HashMap的效率是更好的。
    public static int[] twoSum3(int[] nums , int target){
        Map map = new HashMap<>();
        for(int i =0;i

GPU云服務(wù)器云服務(wù)器 two-sum two sum two.js cdn

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

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

相關(guān)文章

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 2019-08-14 17:01 評(píng)論0 收藏0
leetcode 1 Two Sum Java & JavaScript解法

摘要：返回這兩個(gè)元素的位置。每個(gè)輸入都有且僅有一組滿足條件的元素。想法如果使用蠻力法可以簡(jiǎn)單的解決這個(gè)問(wèn)題。但是需要兩層循環(huán)，效率低。用來(lái)存儲(chǔ)，每一個(gè)元素和目標(biāo)元素的差值和這個(gè)元素的位置。因?yàn)槔锏膶?duì)象也是鍵值對(duì)。題目詳情 Given an array of integers, return indices of the two numbers such that they add up t...

Guakin_Huang 2019-08-22 14:56 評(píng)論0 收藏0
leetcode 1 Two Sum Java & JavaScript解法

摘要：返回這兩個(gè)元素的位置。每個(gè)輸入都有且僅有一組滿足條件的元素。想法如果使用蠻力法可以簡(jiǎn)單的解決這個(gè)問(wèn)題。但是需要兩層循環(huán)，效率低。用來(lái)存儲(chǔ)，每一個(gè)元素和目標(biāo)元素的差值和這個(gè)元素的位置。因?yàn)槔锏膶?duì)象也是鍵值對(duì)。題目詳情 Given an array of integers, return indices of the two numbers such that they add up t...

chanjarster 2019-08-15 14:26 評(píng)論0 收藏0
LeetCode.1 兩數(shù)之和(Two Sum)(JS)

摘要：開(kāi)坑，以后每周刷一兩道一題目?jī)蓴?shù)之和給定一個(gè)整數(shù)數(shù)組和一個(gè)目標(biāo)值，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那兩個(gè)整數(shù)，并返回他們的數(shù)組下標(biāo)。但是，你不能重復(fù)利用這個(gè)數(shù)組中同樣的元素。開(kāi)坑，以后每周刷一兩道LeetCode 一、題目兩數(shù)之和：給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那兩個(gè) 整數(shù)，并返回他們的數(shù)組下標(biāo)。你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)...

Gu_Yan 2019-08-23 16:15 評(píng)論0 收藏0
Leetcode 1：兩數(shù)之和

摘要：給定一個(gè)整數(shù)數(shù)組和一個(gè)目標(biāo)值，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那兩個(gè)整數(shù)，并返回他們的數(shù)組下標(biāo)。示例給定因?yàn)樗苑祷胤椒?，暴力解法。函?shù)可以將一個(gè)數(shù)組轉(zhuǎn)化為一個(gè)從開(kāi)始，值為數(shù)組對(duì)應(yīng)元素的字典。給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那兩個(gè) 整數(shù)，并返回他們的數(shù)組下標(biāo)。你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是，你不能重復(fù)利用這個(gè)數(shù)組中...

Taste 2019-07-31 11:24 評(píng)論0 收藏0