Log

【170409】首次尝试该题不成（提交 01）
【170410】完成该题的 Python 版初步解法（提交 02）
【170412】完成笔记回顾
【170416】看完参考答案并记录思路

题目

3Sum

【题目类型备注】

双指针

提交

01

【语言】

Python

【时间】

170409

【思路】

〖复杂度？〗如果把本题和 Two Sum 联系到一起看，那么很容易联想到：将本题化为 n 个 Two Sum 子问题，第 i 个子问题中的 target 为 -nums[i]（这样，nums[i] 加上之后找到的那对数，正好 3 个数，它们的和为 0，符合题意），搜索的下标范围为 [(i+1):len(nums)]。对于单个 Two Sum（无序）问题，复杂度是 O(n)，因此对于 n 个这样的子问题，总共应该耗费 O(n^2) 的时间复杂度
〖大致流程？〗
从首个元素开始循环
第 i 次循环时，target = -nums[i]，然后在 [(i+1):len(nums)] 的范围内使用 Two Sum 的哈希表解法
每找到一组解，就看看这组解是否已经存在，若不存在，加入答案列表
对 nums[] 中的每个元素进行 2~3 所示的循环
〖什么时候停？〗

每个元素都完成了 Two Sum 哈系表解法时

〖特别注意？〗

需要判断找到的三元组是否已经在答案列表中，需要将每个找到的三元组先进行排序，否则不同顺序、同样元素的三元组将被认为是不同的答案（然而根据题目要求，这样的两组答案算同一组）

〖能否剪枝？〗

暂未发现

【代码】

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        answerList = []
        for (ind, num) in enumerate(nums):
          target = -num
          pair = {}
          for nextNum in nums[(ind+1):]:
            if (nextNum not in pair):
                pair[target-nextNum] = nextNum
            else:
                tempAnswer = [num, pair[nextNum], nextNum]
                tempAnswer.sort()
                if tempAnswer not in answerList:
                    answerList.append(tempAnswer)

        return answerList

【结果】

运行时：Time Limit Exceeded

报告链接：https://leetcode.com/submissions/detail/99582165/

不知道其他拥有 LeetCode 帐号的人能不能看到该报告，所以顺便附图如下：

311 / 313 test cases passed.

略可惜啊，在倒数第 3 个例子前倒下了，超时了……

02

【语言】

Python

【时间】

170410

【思路】

考虑到字典是典型的哈希表数据结构，如果能用字典来存储答案就方便多了；而且靠主键来判断答案是否存在，恐怕耗费的时间会比在二元列表（列表中的元素是列表）中判断答案是否存在，来得少一些（不清楚 Python 解释器如何判断，但稍微思考想象一下，我猜测字符串比较远比二元列表中列表的比较来得容易）。但要如何为每个答案设置主键呢？我想到了常用的字符串散列算法 MD5，SHA256 之类……就用它们来计算 HASH 值吧，然后用它们作为主键。
有一些特殊情况还需要考虑：

若所有的元素符号相同，那么除非这些元素都是 0，否则一定找不到——那么就不用运行下面的算法来寻找答案了
由于我们的算法复杂度是 O(n^2) 的，所以增加这么一次复杂度为 O(n) 的扫描，对大体的运算时间影响是很有限的（理论上是可忽略的）

【代码】

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        import hashlib
        sNums = sorted(nums)
        answerList = []
        answers = {}
        
        if len(nums) < 3:
          return []

        neg = {'last':-1, 'count':0}
        zero = {'last':-1, 'count':0}
        pos = {'last':-1, 'count':0}
        for (ind, item) in enumerate(sNums):
          if item < 0:
            neg['last']=ind
            neg['count']+=1
          elif item == 0:
            zero['last']=ind
            zero['count']+=1
          else:
            pos['last']=ind
            pos['count']+=1

        if len(nums)==neg['count'] or len(nums)==pos['count']:
          return []

        if len(nums)==zero['count']:
          return [[0,0,0]]

        for (ind, num) in enumerate(sNums):
          target = -num
          pair = {}

          for nextNum in sNums[(ind+1):]:
            if (nextNum not in pair):
                pair[target-nextNum] = nextNum
            else:
                tempAnswer = "{},{},{}".format(num, pair[nextNum], nextNum)
                ansKey = hashlib.md5(tempAnswer).hexdigest()
                if ansKey not in answers:
                  answers[ansKey] = [num, pair[nextNum], nextNum]

        answerList = [answers[i] for i in answers]

        return answerList

【结果】

运行时：1438 ms

报告链接：https://leetcode.com/submissions/detail/99694300/

不知道其他拥有 LeetCode 帐号的人能不能看到该报告，所以顺便附图如下：