[leetcode/lintcode 題解] 算法面試真題：三數之和II

描述

輸入 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
解釋：當其中一個為 1，剩下兩個為 0，一共有 1 種方案。           

樣例2
輸入：n = 1
輸出：1
解釋：當 x = 0, y = 0, z = 0 時等式成立。           

找出所有的小于n的完全平方數，套3sum或者确定兩個數然後套二分均可。

public class Solution {
    /**
     * @param n: The n
     * @return: The answer
     */
    public int threeSum2(int n) {
        // Write your code here
        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;
    }
}           

更多題解參考：

九章官網solution