java - HackerEarth 练习时间不多了

Question

我解决了following来自 HackerEarth 的问题。除最后一个测试用异常(exception)，所有测试用例都是正确的，因为它超时了。我尝试优化我的解决方案，但无法更好地优化它。这是我的解决方案:

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

class TestClass {

    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        Set<Integer> perfectNumbers = new HashSet<>();
        for (int i = 0; i <= 20; i++) {
            perfectNumbers.add(i * i * i);
        }
        for (int i = 1; i <= 44; i++) {
            perfectNumbers.add(i * i);
        }

        int t = sc.nextInt();
        for (int k = 0; k < t; k++) {
            int db = 0;
            int n = sc.nextInt();
            int[] a = new int[1001];
            int[] b = new int[1001];
            int[] numbers = new int[n];
            for (int j = 0; j < n; j++) {
                int x = sc.nextInt();
                numbers[j] = x;
                for (Integer perfect : perfectNumbers) {
                    if (x == perfect - x) {
                        b[x]++;
                    } else if (perfect - x >= 0 && perfect - x <= 1000)
                        a[perfect - x]++;
                }
            }
            for (int j = 0; j < n; j++) {
                db += a[numbers[j]];
            }
            for (int j = 0; j <= 1000; j++) {
                if (b[j] > 1) {
                    db += b[j] * (b[j] - 1);
                }
            }

            System.out.println(db / 2);           
        }
    }
}

Answer 1

也许您应该考虑使用一些更快的方法读取输入，因为 Scanner 非常慢。例如，您可以将 Scanner 包装到 BufferedReader 中。
我修改了代码。现在它通过了所有测试用例:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

class TestClass {

    public static void main(String args[]) throws Exception {
        FastReader sc = new FastReader();
        Set<Integer> perfectNumbers = new HashSet<>();
        for (int i = 0; i <= 20; i++) {
            perfectNumbers.add(i * i * i);
        }
        for (int i = 1; i <= 44; i++) {
            perfectNumbers.add(i * i);
        }

        int t = sc.nextInt();
        for (int k = 0; k < t; k++) {
            int db = 0;
            int n = sc.nextInt();
            int[] a = new int[1001];
            int[] b = new int[1001];
            int[] numbers = new int[n];
            for (int j = 0; j < n; j++) {
                int x = sc.nextInt();
                numbers[j] = x;
                for (Integer perfect : perfectNumbers) {
                    if (x == perfect - x) {
                        b[x]++;
                    } else if (perfect - x >= 0 && perfect - x <= 1000)
                        a[perfect - x]++;
                }
            }
            for (int j = 0; j < n; j++) {
                db += a[numbers[j]];
            }
            for (int j = 0; j <= 1000; j++) {
                if (b[j] > 1) {
                    db += b[j] * (b[j] - 1);
                }
            }
            System.out.println(db / 2);
        }
    }


    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            Integer nr=null;
            try {
                nr = Integer.parseInt(next());
            } catch (Exception e) {
                //something went wrong
            }
            return nr;
        }


    }

}