Python Simple Two Sum Solution, time O(n^2) space O(1)


  • 0
    D

    Very similar to two sum problems.

    1. sort input list
    2. If a<=b<=c and a + b > c, then a,b,c can form a triangle. Then problem becomes for each c in nums, count the number of (a, b) pairs so that a + b > c. This can be solved by two sum.
    class Solution(object):
        def triangleNumber(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            nums = sorted(nums)
            res = 0
            for i in range(2, len(nums))[::-1]:
                j, k = 0, i-1
                while j < k:
                    if nums[j] + nums[k] > nums[i]:
                        res += k - j
                        k -= 1
                    else:
                        j += 1
            return res
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.