lintcode 831 · 三数之和 II 【中等 vip 二分】

题目

https://www.lintcode.com/problem/831

输入 n，求所有符合 x^2+y^2+z^2 = n 的 x, y, z 的方案数。（x, y, z为非负整数）


n <= 1000000
x, y, z满足 (x<=y<=z)，只要选择出来的三个数相同就算同一种方案
样例
样例 1：

输入：n = 0
输出：1
解释：当 x = 0, y = 0, z = 0 时等式成立。
样例 2：

输入：n = 1
输出：1
解释：当其中一个为 1，剩下两个为 0，一共有 1 种方案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

思路

找出所有的小于n的完全平方数，套3sum或者确定两个数然后套二分均可
二分法，直接看下面的代码，容易看懂
1
2

答案

public class Solution {
    /**
     * @param n: an integer
     * @return: the number of solutions
     */
    public int threeSum2(int n) {
         //找出所有的小于n的完全平方数，套3sum或者确定两个数然后套二分均可
        int m = (int)Math.round(Math.sqrt(n));
        if(m*m >n){
            m--;
        }
        int ans =0;

        for (int i = 0; i <=m ; i++) {
            int res = n-i*i;
            int left =i,right =m;
            while (left<=right){
                int tmp = left*left+right*right;
                if(tmp > res){
                    right--;
                }else if(tmp < res){
                    left++;
                }else{
                    ans++;
                    left++;
                }
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31