# 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)

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

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.
```

Github: code.dennyzhang.com
Credits To: LintCode.com

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

```## Blog link: https://code.dennyzhang.com/3sum-ii
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
else:
l += 1
return res
```

Share It, If You Like It.