LC.P2465[不同的平均值数目]

方法一：排序+哈希表

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int distinctAverages(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        Set<Integer> set = new HashSet<>();
        for (int i = 0, j = n - 1; i < j; ++i, --j) {
            set.add(nums[i] + nums[j]);
        }
        return set.size();
    }
}
  • 时间复杂度：$O(nlogn)$
  • 空间复杂度：$O(n)$