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)

 Notice
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
Have you met this question in a real interview? 
Example
Given n = 0, return 1.

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

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



class Solution:
    """
    @param n: an integer
    @return: the number of solutions
    """
    #如果直接套用3sum的算法，如果n很大，需要n平方的复杂度
    #因为题目要求 x^2 + y^2 + z^2 = n则 x, y, z一定小于 根号n
    #所以可以枚举小于等于n的所有完全平方数并且放入数组，套用3sum的算法
    #时间复杂度会变为 根号n * 根号n，所以就是 n



    def threeSum2(self, n):
        # Write your code here
        sqrts = []
        for i in range(n + 1):
            if i * i <= n:
                sqrts.append(i * i)
            else:
                break
        print sqrts
        count = 0
        for i in range(len(sqrts)):
            l = i
            r = len(sqrts) - 1
            while l <= r:
                value = sqrts[l] + sqrts[r] + sqrts[i]
                if  value == n:
                    count += 1
                    r -= 1
                    l += 1
                elif value < n:
                    l += 1
                else:
                    r -= 1
        return count