【Leetcode 每日一题 - 补卡】1534. 统计好三元组

问题背景

给你一个整数数组 $arr$，以及 $a、b、c$ 三个整数。请你统计其中好三元组的数量。
如果三元组 $(arr[i],arr[j],arr[k])$ 满足下列全部条件，则认为它是一个 好三元组 。

• $0\le i<j<k<arr.length$
• $|arr[i]-arr[j]|\le a$
• $|arr[j]-arr[k]|\le b$
• $|arr[i]-arr[k]|\le c$

其中 $|x|$ 表示 $x$ 的绝对值。
返回 好三元组的数量 。

数据约束

• $3\le arr.length\le 100$
• $0\le arr[i]\le 1000$
• $0\le a,b,c\le 1000$

解题过程

题中要求的约束有三个，暴力枚举的时间复杂度是 $O(N^3)$。
如果数组是有序的，那可以很容易地提高时间方面的效率，但是结果与元素的初始位置有关，所以不方便直接排序。
退而求其次，定义一个下标数组，对它进行排序。
然后将数组中的元素当作 $j$ 来遍历，将满足 $|arr[i]-arr[j]|\le a$ 以及 $|arr[j]-arr[k]|\le b$
两个条件的原数组中的元素分别记录到哈希表中。
接下来只要再求满足第三个条件的元素对的数量，根据绝对值的定义，可以在线性的时间内得到合法结果的上下限。

具体实现

class Solution {public int countGoodTriplets(int[] arr, int a, int b, int c) {Integer[] idx = new Integer[arr.length];Arrays.setAll(idx, i -> i);Arrays.sort(idx, (i, j) -> arr[i] - arr[j]);int res = 0;for (int j : idx) {int cur = arr[j];List<Integer> list1 = new ArrayList<>();for (int i : idx) {if (i < j && Math.abs(arr[i] - cur) <= a) {list1.add(arr[i]);}}List<Integer> list2 = new ArrayList<>();for (int k : idx) {if (k > j && Math.abs(arr[k] - cur) <= b) {list2.add(arr[k]);}}int left = 0;int right = 0;for (int item : list1) {while (right < list2.size() && list2.get(right) <= item + c) {right++;}while (left < list2.size() && list2.get(left) < item - c) {left++;}res += right - left;}}return res;}
}