讨论/技术交流/Leetcode18.四数之和有关问题/
Leetcode18.四数之和有关问题
class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        list =[]

        def methodTwo(list):
            tempList = []
            for i in list:
                if not i in tempList:
                    tempList.append(i)
            return tempList

        def quick_sort(nums):
            if nums == []:
                return []
            else:
                first = nums[0]
                left = quick_sort([l for l in nums[1:] if l < first])
                right = quick_sort([r for r in nums[1:] if r >= first])
                return left + [first] + right

        nums = quick_sort(nums)
        for i in range(0, len(nums)):
            for j in range(i + 1, len(nums)):
                x = j + 1
                y = len(nums) - 1
                while x < y:
                    if nums[x]+nums[y]+nums[i]+nums[j] == target:
                        templist = []
                        templist.extend((nums[x],nums[y],nums[i],nums[j]))
                        list.append(templist)
                        y = y - 1

                    elif nums[x]+nums[y]+nums[i]+nums[j] < target:
                        x = x + 1
                    elif nums[x]+nums[y]+nums[i]+nums[j] > target:
                        y = y - 1
        return methodTwo(list)

用了双指针耗时1216ms,那块还能缩减一下时间,望指教。

共 1 个回复

排序的话,直接调用编程语言内置的排序函数就好了,一般情况下自己写的排序函数没有内置的稳定高效,剩下的可以看看这个。
https://leetcode-cn.com/problems/4sum/solution/shi-zhan-15san-shu-zhi-he-18si-shu-zhi-h-pp08/