HackerRank Count Triplets问题：编译错误及结果异常求助

Hey there! Let's break down what's going wrong with your code and fix it step by step. First off, I can see you've already sorted out the compile errors (switching from length() to size() and using get() for List access), which is great—now the main issue is a logic mistake that's making all test cases return 0, plus we can talk about performance for larger inputs.

1. Core Logic Error: Confusing Geometric vs. Arithmetic Sequences #

The problem asks for triplets that form a geometric sequence with common ratio r. That means:

• The second element should be the first multiplied by r: arr[j] = arr[i] * r
• The third element should be the second multiplied by r: arr[k] = arr[j] * r

But your code is checking for an arithmetic sequence (difference of r) with these lines:

if (arr.get(j) - arr.get(i) == r) {
    // ...
    if (arr.get(k) - arr.get(j) == r) {

That's why all test cases return 0—you're looking for the wrong pattern entirely!

Fixed Basic Version (Works for Small Inputs) #

Here's your code with the corrected logic, plus a small tweak to avoid integer overflow (using long for the counter instead of int):

import java.io.*;
import java.util.*;
import java.util.stream.*;

public class Solution {
    // Complete the countTriplets function below.
    static long countTriplets(List<Long> arr, long r) {
        long counter = 0; // Use long to handle large triplet counts
        int n = arr.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (arr.get(j) == arr.get(i) * r) {
                    for (int k = j + 1; k < n; k++) {
                        if (arr.get(k) == arr.get(j) * r) {
                            counter++;
                        }
                    }
                }
            }
        }
        return counter;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] nr = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

        int n = Integer.parseInt(nr[0]);
        long r = Long.parseLong(nr[1]);

        List<Long> arr = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
            .map(Long::parseLong)
            .collect(Collectors.toList());

        long ans = countTriplets(arr, r);

        bufferedWriter.write(String.valueOf(ans));
        bufferedWriter.newLine();

        bufferedReader.close();
        bufferedWriter.close();
    }
}

2. Performance Optimization for Large Inputs #

The above fixed code will work for small test cases, but its O(n³) time complexity will be way too slow for large arrays (like n = 10^5). Let's optimize this to O(n) time using hash maps to track counts as we iterate:

import java.io.*;
import java.util.*;
import java.util.stream.*;

public class Solution {
    static long countTriplets(List<Long> arr, long r) {
        // rightMap: counts how many times each number appears to the right of current index
        Map<Long, Long> rightMap = new HashMap<>();
        // middleMap: counts how many valid (x, current) pairs exist for current to be the middle element
        Map<Long, Long> middleMap = new HashMap<>();
        long tripletCount = 0;

        // Traverse from the end of the array to the start
        for (int i = arr.size() - 1; i >= 0; i--) {
            long current = arr.get(i);
            long next = current * r;

            // 1. Current can be the first element of a triplet: add all valid (next, next*r) pairs from middleMap
            tripletCount += middleMap.getOrDefault(next, 0L);

            // 2. Current can be the middle element: add count of next in rightMap to middleMap
            middleMap.put(current, middleMap.getOrDefault(current, 0L) + rightMap.getOrDefault(next, 0L));

            // 3. Update rightMap with current element
            rightMap.put(current, rightMap.getOrDefault(current, 0L) + 1);
        }

        return tripletCount;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] nr = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

        int n = Integer.parseInt(nr[0]);
        long r = Long.parseLong(nr[1]);

        List<Long> arr = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
            .map(Long::parseLong)
            .collect(Collectors.toList());

        long ans = countTriplets(arr, r);

        bufferedWriter.write(String.valueOf(ans));
        bufferedWriter.newLine();

        bufferedReader.close();
        bufferedWriter.close();
    }
}

How the Optimized Version Works: #

• We traverse from right to left, keeping track of:
  1. rightMap: How many times each number exists in the part of the array we've already processed (to the right of current index).
  2. middleMap: How many valid pairs (x, y) exist where y = x * r—this helps us quickly count how many triplets can be formed with the current element as the first item.
• For each element, we calculate how many triplets it can start by looking up current * r in middleMap, then update our maps for the next (leftward) element.

Recap of Your Initial Compile Errors (Just for Reference) #

You already fixed these, but let's confirm:

• arr.length(): List uses size() method instead of length() (arrays use the length property, not a method).
• arr[j]: List elements are accessed with get(j), not array-style brackets.

内容的提问来源于stack exchange，提问作者Dark_Foxx