分析

先读题目，我们可以分析出几个点
1. 题目肯定有解，即一定可以表示成 $a^2 + b^2 + c^2 + d^2 = n$
2. 求的是字典序最小的解法，即a <= b <= c <= d

分析出这些条件我们就可以着手找思路了

首先，我们很容易想到暴力法，
四重循环，遍历abcd，这样时间复杂度$O(n^4)$，显然超时，代码就不贴了。
然后思考暴力的优化，根据我们两数之和的题目，我们能够想到a,b,c,n都确定了，那么可以计算出d，这样就少了一层循环，变成了O(n^3)。
很好，又优化了，让我们看看还能不能优化，答案是可以！
我们要求的是字典序最小的，因此我们每次遍历最大值不必是[0, n]，每一层的起使都是上一次的数，到sqrt(n)
最后一层判断是否超过，超过就break掉。
暴力法优化到这里在蓝桥杯中其实已经能过了，但是y总加强了数据，暴力法已经不能过了
时间复杂度$O(n^{3/2})$

hash+枚举

根据刚刚优化掉一重循环的思想，考虑我们能不能再优化掉一重，答案是可以，我们可以先计算c^2 + d^2,将c^2+d^2存起来，那样我们只需要计算$a^2 + b^2$的值，寻找$n - a^2 + b^2$存不存在就可以找出结果，所以我们可以借助hash表，将$c^2 + d^2$作为key，c的索引+1作为值(索引+1可以让我们不用给hash表填充-1，我们使用的是数组代替hash，具体见代码),这样就可以得出a，b，c，d了
时间复杂度$O(n)$

暴力优化

import java.util.*;

class Main{

    static int[] map;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        for(int a = 0; a * a <= n; a++) {
            int a2 = a * a;
            for(int b = a; a2 + b * b <= n; b ++) {
                int b2 = b * b;
                for(int c = b; c * c + a2 + b2 <= n; c++) {
                    int t = (int)Math.sqrt(n - c * c - a2 - b2);
                    if(a2 + b2 + c * c + t * t == n) {
                        System.out.println(a + " " + b + " " + c + " " + t);
                        return;
                    }
                }
            }
        }
    }
}

hash+枚举

import java.util.*;

class Main{

    static int[] map;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        map = new int[5 * 1000000 + 10];

        // 先打表，存c^2 + d^2
        for(int c = 0; c * c * 2<= n; c++) {
            for(int d = c; c * c + d * d <= n; d++) {
                if(map[c*c + d*d] == 0) map[c*c + d*d] = c + 1; // 这样就不用遍历map赋值-1了，因为数组可能会用到0
            }
        }

        for(int a = 0; a * a <= n / 4; a++) {
            for(int b = a; a * a + b * b <= n / 2; b++) {
                int t = n - a * a - b * b;
                if(map[t] != 0) { // 存在a2 + b2 + c2 + d2 == n
                    int c = map[t] - 1;
                    int d = (int)Math.sqrt(n - a*a - b*b - c*c);
                    System.out.println(a + " " + b + " " + c + " " + d);
                    return;
                }
            }
        }
    }
}