15. 3Sum.md

15. 3Sum

https://leetcode.com/problems/3sum/

solution

• 注意去重

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) < 3:
            return []

        nums.sort()
        res = []

        for i in range(len(nums)):
            if nums[i] > 0:
                break

            if i > 0 and nums[i] == nums[i-1]:  # 第一个元素去重, 前面有for所以用if
                continue

            l = i + 1
            r = len(nums) - 1

            while l < r:
                total = nums[l] + nums[r] + nums[i]
                if total > 0:
                    r -= 1
                elif total < 0:
                    l += 1
                elif total == 0:
                    res.append([nums[i], nums[l], nums[r]])
                    l += 1
                    r -= 1

                    while l < r and nums[l-1] == nums[l]: # 注意去重的位置和写法，注意不是continue, 以及while, 以及是相等时才处理
                        l += 1
                    while l < r and nums[r+1] == nums[r]:
                        r -= 1
        return res

时间复杂度：O(n^2)
空间复杂度：O(1)

follow up

611. Valid Triangle Number

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        if len(nums) < 3:
            return 0

        nums.sort()
        res = 0
        for i in range(len(nums)):
            j = 0
            k = i - 1
            while j < k:
                if nums[j] + nums[k] > nums[i]:
                    res += k - j  # 注意: all pairs starting from i up to j-1 with j as the second element can form a valid triangle with k as the longest side
                    k -= 1
                else:
                    j += 1
        return res