三元組相加獲得target

Joyven 發布于2019-07-25 12:04 / 1031人閱讀

摘要：三元組相加獲得給定一個數組，選擇三個元素相加，結果為，找出所有符合的三元組思路亂序數組，需要找到所有組合，需要三層循環，復雜度為。需要避免重復的三元組被加入代碼避免重復避免重復本題以及其它題目代碼地址地址

三元組相加獲得target 3Sum

給定一個數組，選擇三個元素相加，結果為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]
]

思路

亂序數組，需要找到所有組合，需要三層循環，復雜度為O(n3)。

可以先排序，排序后只需要兩層循環，復雜度為O(n2)。第一層循環遍歷所有元素，第二層循環由于數組已經排序，只需要頭尾兩個指針像中間靠攏，一但三個元素相加為target，則添加此三元組，然后繼續像中間靠攏掃描。

需要避免重復的三元組被加入

代碼

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):
            # 避免重復
            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
                    # 避免重復
                    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地址

GPU云服務器云服務器構造三元組java版 java二位數組相加 target target roject

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/38669.html

三元組相加獲得結果最接近target

摘要：三元組相加獲得結果最接近給定一個數組，選擇三個元素相加，結果必須為所有三元組中最接近的值，返回這個三元組的和。思路思路參照三元組相加獲得只需要將上述文章思路中換成第二次循環找到三元組的和最接近的組合即可。代碼本題以及其它題目代碼地址地址三元組相加獲得結果最接近target 3SumClosest 給定一個數組，選擇三個元素相加，結果必須為所有三元組中最接近target的值，返回這個...

lmxdawn 2019-07-25 12:04 評論0 收藏0
四元組相加獲得target

摘要：四元組相加獲得給定一個數組，選擇四個元素相加，結果為，找出所有符合的四元組。思路思路參照三元組相加獲得多一層循環即可，注意邊界檢測即可。代碼本題以及其它題目代碼地址地址四元組相加獲得target 4Sum 給定一個數組，選擇四個元素相加，結果為target，找出所有符合的四元組。 Given an array S of n integers, are there elements ...

sunsmell 2019-07-25 12:04 評論0 收藏0
JS算法題之leetcode(11~20)

摘要：給定一個整數，將其轉為羅馬數字。字符數值例如，羅馬數字寫做，即為兩個并列的。通常情況下，羅馬數字中小的數字在大的數字的右邊。給定一個羅馬數字，將其轉換成整數。注意空字符串可被認為是有效字符串。 JS算法題之leetcode(11~20) showImg(https://segmentfault.com/img/bVbwmfg?w=1790&h=714);這次的十道題目都比較容易，我們簡...

CoderDock 2019-08-26 10:46 評論0 收藏0
AI是如何回答你提出的問題的？揭秘智能問答系統背后的深度學習網絡

摘要：人類如何回答問題在考慮設計一個問答系統之前，不妨先來考慮一下人類是如何回答問題的。問答的各個子系統都可以用深度學習實現。摘要：隨著人工智能和物聯網技術的飛速發展和相互融合，越來越多的設備將會被植入問答AI，未來問答將會成為人機交互的重要入口，AI問答將會無處不在。那么AI是如何回答你所提出的問題的？本文就為你揭秘智能問題系統背后的深度學習網絡架構設計以及原理。本文內容由演講嘉賓視頻...

curried 2019-06-26 18:23 評論0 收藏0