java算法数字游戏特殊的数

Question

　　2021 是一个非常特殊的数，它可以表示成两个非负整数的平方差，2021 = 45 * 45 - 2 * 2。
　　2025 也是同样特殊的数，它可以表示成 2025 = 45 * 45 - 0 * 0。
　　请问，在 1 到 2021 中有多少个这样的数？
　　请注意，有的数有多种表示方法，例如 9 = 3 * 3 - 0 * 0 = 5 * 5 - 4 * 4，在算答案时只算一次。
结果只要一个整数

Answer 1

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        System.out.println(main.getDiffCnt(2021));
}
    private int getDiffCnt(int max){
        List<Integer> subs = new ArrayList<>();
        int prev = 0;
        //先求平方i的平方，假设当前和后续的平方差大于最大值，说明后续没有需要的值了
        for(int i = 0,curr; prev+max>=(curr = i*i); i++){
            subs.add(curr);
            prev = curr;
        }

        //也可以用哈希，稠密度比较高，用数组更好
        boolean [] specials = new boolean[max+1];
        int n = subs.size();
        for(int i = 0; i < n-1; i++){
            //剪枝，当差值大于最大时，后续没有需要的值了，结束内循环
            for(int j = i+1; j < n&&subs.get(j)-subs.get(i)<=max; j++){
                specials[subs.get(j)-subs.get(i)]=true;
            }
        }

        //计算数目
        int cnt = 0;
        for(int i = 1; i <= max; i++){
            if(specials[i])
                ++cnt;
        }
//       System.out.println(Arrays.toString(specials));
        return cnt;

    }
}