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

資訊專(zhuān)欄INFORMATION COLUMN

從數(shù)組中尋找和的相加數(shù)

Astrian / 1038人閱讀

摘要：從數(shù)組中尋找和的相加數(shù)思路這個(gè)題目簡(jiǎn)單，兩個(gè)循環(huán)嵌套可以實(shí)現(xiàn)，但是考慮到輸入數(shù)組長(zhǎng)度大的情況下，時(shí)間復(fù)雜度太高使用索引，遍歷一次后記錄中所有數(shù)字出現(xiàn)的下標(biāo)，用得到，然后直接查索引中的位置索引可以用數(shù)組，但是中可能會(huì)有大數(shù)

從數(shù)組中尋找和的相加數(shù) Two Sum

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 1

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

example 2

Given nums = [0,4,3,0], target = 0,

Because nums[0] + nums[3] = 0 + 0 = 0,
return [0, 3].

example 3

Given nums = [-1,-2,-3,-4,-5], target = -8,

Because nums[2] + nums[4] = -3 + (-5) = -8,
return [2, 4].

example 4

Given nums = [0,1,2,3,4,5,...,28888,...,65432], target = 65432,

you should consider that time and space is limited.
思路

這個(gè)題目簡(jiǎn)單，兩個(gè)for循環(huán)嵌套可以實(shí)現(xiàn)，但是考慮到輸入數(shù)組長(zhǎng)度大的情況下，時(shí)間復(fù)雜度太高, O(n2)

使用索引，遍歷一次后記錄nums中所有數(shù)字出現(xiàn)的下標(biāo)，用target - nums[i]得到j(luò)，然后直接查索引中j的位置

索引可以用list(數(shù)組)，但是nums中可能會(huì)有大數(shù)字，所需的空間太多，并且會(huì)有負(fù)數(shù)，改用dir，key為nums[i]，value為i

同時(shí)給出簡(jiǎn)單版代碼（簡(jiǎn)單版在java，C等語(yǔ)言在leetcode網(wǎng)站可以AC，但python會(huì)超時(shí)）

代碼

優(yōu)化版

class Solution:

    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        idx_set = {}
        for i, item in enumerate(nums):
            idx = target - nums[i]
            if idx in idx_set:
                j = idx_set[idx]
                if len(j) != 0 and j[0] != i:
                    return list([i, j[0]])
                if j[0] == i and len(j) > 1:
                    return list([i, j[1]])
            else:
                idx_set[item] = [i]

簡(jiǎn)單版

class Solution:

    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return list([i, j])

本題以及其它leetcode題目代碼github地址: github地址

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

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

相關(guān)文章

  • LeetCode 2：兩數(shù)相加 Add Two Numbers

    摘要：給出兩個(gè)非空的鏈表用來(lái)表示兩個(gè)非負(fù)的整數(shù)。如果，我們將這兩個(gè)數(shù)相加起來(lái)，則會(huì)返回一個(gè)新的鏈表來(lái)表示它們的和。需要考慮到兩個(gè)鏈表長(zhǎng)度不同時(shí)遍歷方式鏈表遍歷完成時(shí)最后一位是否需要進(jìn)一位。 ?給出兩個(gè) 非空 的鏈表用來(lái)表示兩個(gè)非負(fù)的整數(shù)。其中，它們各自的位數(shù)是按照 逆序 的方式存儲(chǔ)的，并且它們的每個(gè)節(jié)點(diǎn)只能存儲(chǔ) 一位 數(shù)字。如果，我們將這兩個(gè)數(shù)相加起來(lái)，則會(huì)返回一個(gè)新的鏈表來(lái)表示它們的和。 ...

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

  • LeetCode 2：兩數(shù)相加 Add Two Numbers

    摘要：給出兩個(gè)非空的鏈表用來(lái)表示兩個(gè)非負(fù)的整數(shù)。如果，我們將這兩個(gè)數(shù)相加起來(lái)，則會(huì)返回一個(gè)新的鏈表來(lái)表示它們的和。需要考慮到兩個(gè)鏈表長(zhǎng)度不同時(shí)遍歷方式鏈表遍歷完成時(shí)最后一位是否需要進(jìn)一位。 ?給出兩個(gè) 非空 的鏈表用來(lái)表示兩個(gè)非負(fù)的整數(shù)。其中，它們各自的位數(shù)是按照 逆序 的方式存儲(chǔ)的，并且它們的每個(gè)節(jié)點(diǎn)只能存儲(chǔ) 一位 數(shù)字。如果，我們將這兩個(gè)數(shù)相加起來(lái)，則會(huì)返回一個(gè)新的鏈表來(lái)表示它們的和。 ...

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

  • Leetcode724：尋找數(shù)組的中心索引（java、python3）

    摘要：尋找數(shù)組的中心索引給定一個(gè)整數(shù)類(lèi)型的數(shù)組，請(qǐng)編寫(xiě)一個(gè)能夠返回?cái)?shù)組中心索引的方法。同時(shí)也是第一個(gè)符合要求的中心索引。示例輸入輸出解釋數(shù)組中不存在滿足此條件的中心索引。說(shuō)明的長(zhǎng)度范圍為。 尋找數(shù)組的中心索引 給定一個(gè)整數(shù)類(lèi)型的數(shù)組 nums，請(qǐng)編寫(xiě)一個(gè)能夠返回?cái)?shù)組中心索引的方法。 我們是這樣定義數(shù)組中心索引的：數(shù)組中心索引的左側(cè)所有元素相加的和等于右側(cè)所有元素相加的和。 如果數(shù)組不存在中心...

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

  • Leetcode724：尋找數(shù)組的中心索引（java、python3）

    摘要：尋找數(shù)組的中心索引給定一個(gè)整數(shù)類(lèi)型的數(shù)組，請(qǐng)編寫(xiě)一個(gè)能夠返回?cái)?shù)組中心索引的方法。同時(shí)也是第一個(gè)符合要求的中心索引。示例輸入輸出解釋數(shù)組中不存在滿足此條件的中心索引。說(shuō)明的長(zhǎng)度范圍為。 尋找數(shù)組的中心索引 給定一個(gè)整數(shù)類(lèi)型的數(shù)組 nums，請(qǐng)編寫(xiě)一個(gè)能夠返回?cái)?shù)組中心索引的方法。 我們是這樣定義數(shù)組中心索引的：數(shù)組中心索引的左側(cè)所有元素相加的和等于右側(cè)所有元素相加的和。 如果數(shù)組不存在中心...

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

  • 70道前端LeetCode題目集合及視頻講解（持續(xù)更新中...）

    前端LeetCode刷題 下面是已刷的題目的目錄。GitHub：https://github.com/cunzaizhuy...每日打卡更新中，歡迎關(guān)注。 數(shù)組類(lèi) 26 刪除排序數(shù)組中的重復(fù)項(xiàng) 27 移除元素 35 搜索插入位置 66 加1 80 medium 刪除排序數(shù)組中的重復(fù)項(xiàng)2 88 合并兩個(gè)有序數(shù)組 167 兩數(shù)之和II - 輸入有序數(shù)組 118 楊輝三角 169 easy 求眾數(shù) 1...

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

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

0條評(píng)論

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