四元组相加获得target

sunsmell 发布于2019-07-25 12:04 / 2519人阅读

摘要：四元组相加获得给定一个数组，选择四个元素相加，结果为，找出所有符合的四元组。思路思路参照三元组相加获得多一层循环即可，注意边界检测即可。代码本题以及其它题目代码地址地址

四元组相加获得target 4Sum

给定一个数组，选择四个元素相加，结果为target，找出所有符合的四元组。

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate triplets.

example 1

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

思路

思路参照三元组相加获得target

多一层循环即可，注意边界检测即可。

代码

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        nums.sort()
        ret = []
        for i in range(len(nums) - 3):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            for j in range (i+1, len(nums) - 2):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                head, tail = j+1, len(nums) - 1
                while head < tail:
                    if nums[i] + nums[j] + nums[head] + nums[tail] == target:
                        ret.append([nums[i], nums[j], nums[head], nums[tail]])
                        head += 1
                        tail -= 1
                        while head < tail and nums[head] == nums[head - 1]:
                            head += 1
                        while head < tail and nums[tail] == nums[tail + 1]:
                            tail -= 1
                    elif nums[i] + nums[j] + nums[head] + nums[tail] > target:
                        tail -= 1
                    else:
                        head += 1
        return ret

本题以及其它leetcode题目代码github地址: github地址

云服务器 GPU云服务器四元组四元vps target 四元式序列c语言实现

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

转载请注明本文地址：https://www.ucloud.cn/yun/38666.html

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
LeetCode18.四数之和 JavaScript

摘要：给定一个包含个整数的数组和一个目标值，判断中是否存在四个元素，，和，使得的值与相等找出所有满足条件且不重复的四元组。满足要求的四元组集合为答案参考先排序第一个第二个第三个给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的...

antyiwei 2019-08-23 15:16 评论0 收藏0
万人千题计划-32

摘要：假设模式起始位置为，判断后续序列是否满足条件，其实只需要判断与是否相同。如果数组中不存在至少重复次且长度为的模式，返回注意这里需要加一，否则会错万人千题计划今...

galois 2021-11-22 09:34 评论0 收藏0
以太坊数据结构MPT

摘要：是以太坊存储数据的核心数据结构，它是由和结合的一种树形结构，理解有助于我们更好的理解以太坊的数据存储。所以就有了树压缩前缀树，后面会介绍到，也被称为，中文名称默克尔树，主要用于数据集较大时的文件校验。 MPT(Merkle Patricia Tries)是以太坊存储数据的核心数据结构，它是由Merkle Tree和Patricia Tree结合的一种树形结构，理解MPT有助于我们更...

Honwhy 2019-06-27 18:59 评论0 收藏0
以太坊源码分析--MPT树

摘要：是以太坊中存储区块数据的核心数据结构，它和融合一个树形结构，理解结构对之后学习以太坊区块以及智能合约状态存储结构的模块源码很有帮助。 MPT(Merkle Patricia Tries)是以太坊中存储区块数据的核心数据结构，它Merkle Tree和Patricia Tree融合一个树形结构，理解MPT结构对之后学习以太坊区块header以及智能合约状态存储结构的模块源码很有帮助。首...

roadtogeek 2019-06-27 18:35 评论0 收藏0