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

  • 0

    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
                        j += 1
            return res

Log in to reply

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