三元组相加获得target

Joyven 发布于2019-07-25 12:04 / 881人阅读

摘要：三元组相加获得给定一个数组，选择三个元素相加，结果为，找出所有符合的三元组思路乱序数组，需要找到所有组合，需要三层循环，复杂度为。需要避免重复的三元组被加入代码避免重复避免重复本题以及其它题目代码地址地址

三元组相加获得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(n³)。

可以先排序，排序后只需要两层循环，复杂度为O(n²)。第一层循环遍历所有元素，第二层循环由于数组已经排序，只需要头尾两个指针像中间靠拢，一但三个元素相加为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地址

云服务器私有云构造三元组java版 java二位数组相加 target target roject

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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