8.13 美团笔试 第四题

/**
 * 给一个数组，nums, 要求找到所有满足下列条件的三元组的“个数”
 * 1) i < j < k 
 * 2) nums[i] - nums[j] = 2nums[j] - nums[k]
 * 思路：
 * 条件2转化为nums[i] + nums[k] = 3nums[j]
 * 遍历i=0..n - 2, k = i + 2..n
 * 期间维护一个map，记录nums区间(i,j) 每一个值的个数，然后将值为 (nums[i] + nums[k]) / 3（要能够整除）的个数记录
 * 最后的数目就是结果
 */
public class Main_4 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        final int n = sc.nextInt();
        int[] values = new int[n];
        for (int i = 0;i < n;++i) {
            values[i] = sc.nextInt();
        }
        long result = 0;
        for (int i = 0;i < n - 2;++i) {
            // map记录   值--个数
            Map<Integer,Integer> map = new HashMap<>();
            map.put(values[i + 1], 1);
            for (int k = i + 2;k < n;++k) {
                int target = (values[i] + values[k]);
                if (target % 3 == 0) {
                    result += map.getOrDefault(target / 3, 0);
                }
                // 到这里，values[k]可以被添加到map中了
                map.put(values[k], map.getOrDefault(values[k], 0) + 1);
            }
        }
        System.out.println(result);
    }
}