LintCode: 3Sum II

3Sum II

Similar Problems:

Given n, find the number of solutions for all x, y, z that conforms to x^2+y^2+z^2 = n.(x, y, z are non-negative integers)


  • n <= 1000000
  • x, y, z satisfy (x <= y <= z), we can consider that is the same solution as long as the three numbers selected are the same


Given n = 0, return 1.

When x = 0, y = 0, z = 0, the equation holds.
Given n = 1, return 1.

When one of them is 1 and the remaining two are 0, there is a total of 1 solution.

Credits To:

Leave me comments, if you have better ways to solve.

## Blog link:
class Solution:
    @param n: an integer
    @return: the number of solutions
    def threeSum2(self, n):
        ## Basic Ideas:
        ## Complexity: Time O(n*n), Space O(1)
        import math
        nums = [x*x for x in range(1001)]
        res = 0

        max = int(math.sqrt(n))
        for i in range(max+1):
            l, r = i, max
            while l<=r:
                v = nums[i]+nums[l]+nums[r]
                if v == n:
                    res += 1
                    l += 1
                elif v>n:                
                    r -= 1
                    l += 1
        return res

Share It, If You Like It.

Leave a Reply

Your email address will not be published.