P1 三数之和 LeetCode15

字数统计: 597字 | 阅读时长: 2分

2019-08-20

P1三数之和，难度中等，相关标签为数组、双指针。

题目

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

LeetCode题目链接https://leetcode-cn.com/problems/3sum/

解题思路

暴力解法三重循环

from collections import Counter
class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        ls = []
        for i, a in enumerate(nums):
            for j, b in enumerate(nums[i+1:]):
                for _, c in enumerate(nums[j+i+2:]):
                    if a + b + c == 0 and Counter([a, b, c]) not in ls:
                            ls.append(Counter([a, b, c]))
        for i in ls:
            result.append(list(i.elements()))
        for i in result:
            i.sort()
        result.sort()
        return result


s = Solution()
ss = s.threeSum([-1, 0, 1, 2, -1, -4])
print(ss)

输出：

1	[[-1, -1, 2], [-1, 0, 1]]

时间复杂度为
$$
O(n^3)
$$

哈希表

class Solution:
    def threeSum(self, nums):
        nums_hash = {}
        result = list()
        for num in nums:  # 计算列表中每个值出现次数
            nums_hash[num] = nums_hash.get(num, 0) + 1
        if 0 in nums_hash and nums_hash[0] >= 3:  # 0的次数大于3，追加
            result.append([0, 0, 0])

        neg = list(filter(lambda x: x<0, nums_hash))  # 存储<0
        pos = list(filter(lambda x: x>=0, nums_hash))  # 存储>=0

        for i in neg:
            for j in pos:
                dif = 0 - i - j
                if dif in nums_hash:  # 目标出现在nums_hash中
                    if dif in (i, j) and nums_hash[dif] >= 2:
                        result.append([i, j, dif])
                    if dif < i or dif > j:
                        result.append([i, j, dif])
        return result

s = Solution()
ss = s.threeSum([-1, 0, 1, 2, -1, -4])
print(ss)

输出：

1	[[-1, -1, 2], [-1, 0, 1]]

时间复杂度为
$$
O(n^2)
$$

积累

enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中。

1	enumerate(sequence, [start=0])

seasons = [‘Spring’, ‘Summer’, ‘Fall’, ‘Winter’]

list(enumerate(seasons))
[(0, ‘Spring’), (1, ‘Summer’), (2, ‘Fall’), (3, ‘Winter’)]

list(enumerate(seasons, start=1)) # 下标从 1 开始
[(1, ‘Spring’), (2, ‘Summer’), (3, ‘Fall’), (4, ‘Winter’)]

class collections.Counter([iterable-or-mapping])

Counter 集成于 dict 类，因此也可以使用字典的方法，此类返回一个以元素为 key 、元素个数为 value 的 Counter 对象集合。

from collections import Counter
s = “hello pinsily”
d = Counter(s)

d
Counter({‘l’: 3, ‘i’: 2, ‘h’: 1, ‘e’: 1, ‘o’: 1, ‘ ‘: 1, ‘p’: 1, ‘n’: 1, ‘s’: 1, ‘y’: 1})

本文作者： Yao Zhu
发布时间： 2019-08-20
最后更新： 2019-12-21
本文链接： https://juoyo.github.io/posts/c415b63f.html
版权声明： 本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处！