資訊專欄INFORMATION COLUMN
摘要：三元組相加獲得給定一個數(shù)組，選擇三個元素相加，結(jié)果為，找出所有符合的三元組思路亂序數(shù)組，需要找到所有組合，需要三層循環(huán)，復(fù)雜度為。需要避免重復(fù)的三元組被加入代碼避免重復(fù)避免重復(fù)本題以及其它題目代碼地址地址
三元組相加獲得target 3Sum
給定一個數(shù)組，選擇三個元素相加，結(jié)果為target，找出所有符合的三元組
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0
Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4]
example 1
input: [-1, 0, 1, 2, -1, -4] A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]思路
亂序數(shù)組，需要找到所有組合，需要三層循環(huán)，復(fù)雜度為O(n3)。
可以先排序，排序后只需要兩層循環(huán)，復(fù)雜度為O(n2)。第一層循環(huán)遍歷所有元素，第二層循環(huán)由于數(shù)組已經(jīng)排序，只需要頭尾兩個指針像中間靠攏，一但三個元素相加為target，則添加此三元組，然后繼續(xù)像中間靠攏掃描。
需要避免重復(fù)的三元組被加入
代碼class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
ret = []
for i in range(len(nums) - 2):
# 避免重復(fù)
if i > 0 and nums[i] == nums[i-1]:
continue
j, k = i + 1, len(nums) - 1
while j < k:
if nums[i] + nums[j] + nums[k] == 0:
ret.append([nums[i], nums[j], nums[k]])
j += 1
k -= 1
# 避免重復(fù)
while j < k and nums[j] == nums[j - 1]:
j += 1
while j < k and nums[k] == nums[k + 1]:
k -= 1
elif nums[i] + nums[j] + nums[k] < 0:
j += 1
else:
k -= 1
return ret
本題以及其它leetcode題目代碼github地址: github地址
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/38669.html
摘要：三元組相加獲得結(jié)果最接近給定一個數(shù)組，選擇三個元素相加，結(jié)果必須為所有三元組中最接近的值，返回這個三元組的和。思路思路參照三元組相加獲得只需要將上述文章思路中換成第二次循環(huán)找到三元組的和最接近的組合即可。代碼本題以及其它題目代碼地址地址 三元組相加獲得結(jié)果最接近target 3SumClosest 給定一個數(shù)組，選擇三個元素相加，結(jié)果必須為所有三元組中最接近target的值，返回這個...
摘要：四元組相加獲得給定一個數(shù)組，選擇四個元素相加，結(jié)果為，找出所有符合的四元組。思路思路參照三元組相加獲得多一層循環(huán)即可，注意邊界檢測即可。代碼本題以及其它題目代碼地址地址 四元組相加獲得target 4Sum 給定一個數(shù)組，選擇四個元素相加，結(jié)果為target，找出所有符合的四元組。 Given an array S of n integers, are there elements ...
摘要：給定一個整數(shù)，將其轉(zhuǎn)為羅馬數(shù)字。字符數(shù)值例如，羅馬數(shù)字寫做，即為兩個并列的。通常情況下，羅馬數(shù)字中小的數(shù)字在大的數(shù)字的右邊。給定一個羅馬數(shù)字，將其轉(zhuǎn)換成整數(shù)。注意空字符串可被認為是有效字符串。 JS算法題之leetcode(11~20) showImg(https://segmentfault.com/img/bVbwmfg?w=1790&h=714);這次的十道題目都比較容易，我們簡...
摘要：人類如何回答問題在考慮設(shè)計一個問答系統(tǒng)之前，不妨先來考慮一下人類是如何回答問題的。問答的各個子系統(tǒng)都可以用深度學(xué)習(xí)實現(xiàn)。 摘要：隨著人工智能和物聯(lián)網(wǎng)技術(shù)的飛速發(fā)展和相互融合，越來越多的設(shè)備將會被植入問答AI，未來問答將會成為人機交互的重要入口，AI問答將會無處不在。那么AI是如何回答你所提出的問題的？本文就為你揭秘智能問題系統(tǒng)背后的深度學(xué)習(xí)網(wǎng)絡(luò)架構(gòu)設(shè)計以及原理。 本文內(nèi)容由演講嘉賓視頻...
閱讀 676·2021-11-24 09:39
閱讀 2343·2021-11-22 13:54
閱讀 2211·2021-09-23 11:46
閱讀 3257·2019-08-30 15:55
閱讀 2692·2019-08-30 15:54
閱讀 2419·2019-08-30 14:18
閱讀 1557·2019-08-29 14:15
閱讀 2745·2019-08-29 13:49
