LeetCode 刷题

Two Sum 两数之和

题目：

有2种解法：

第一种（最trivial的，复杂度$O(n^2)$）：

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                if nums[i]+nums[j]==target:
                    return [i,j]

第二种（复杂度$O(n)$）：

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        d = {}
        for i in range(len(nums)):
            if nums[i] in d:
                return [d[nums[i]], i]
            rest = target - nums[i]
            d[rest] = i

3Sum 三数之和

题目：

思路：先给数组排序，遍历地固定一个数，然后通过维护两个指针来解决剩下来的两数之和问题。记得要去重（非常重要）。

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        nums.sort()
        for i in range(len(nums)-2):
            # 去重
            if i>0 and nums[i]==nums[i-1]:
                continue
                
            left = i+1
            right = len(nums)-1

            while left < right:
                sum = nums[i]+nums[left]+nums[right]
                if sum==0:
                    res.append([nums[i],nums[left],nums[right]])

                    # 这里的2个while循环在去重
                    while left < right and nums[left]==nums[left+1]:
                        left += 1
                    while left < right and nums[right]==nums[right-1]:
                        right -= 1

                    left += 1
                    right -= 1
                elif sum < 0:
                    left += 1
                else:
                    right -= 1
                
        return res

也可以等结尾再去重，但这种方法的空间/时间复杂度会高很多：

class Solution(object):
    def threeSum(self, nums):
        res = []
        nums.sort()

        for i in range(len(nums) - 2):
            left = i + 1
            right = len(nums) - 1

            while left < right:
                total = nums[i] + nums[left] + nums[right]

                if total == 0:
                    res.append([nums[i], nums[left], nums[right]])
                    left += 1
                    right -= 1
                elif total < 0:
                    left += 1
                else:
                    right -= 1

        seen = set()
        ans = []

        for triplet in res:
            t = tuple(triplet)
            if t not in seen:
                seen.add(t)
                ans.append(triplet)

        return ans