刷题记录：哈希表+双指针 | leetcode-2465. 不同的平均值数目 2023/6/4

2465. 不同的平均值数目

这道题挺容易的。主要是排序+哈希。题目里有明显的去重的意思，所以哈希set是肯定有的。找最大最小，最方便的就是排序。这里我为了操作方便，把数组nums拷贝到了集合list里面。排一次序，之后取最大值最小值都很方便。

Collections.sort()方法，可以给Collection集合排序。

我的答案是这样：

class Solution {
    Set<Double> set = new HashSet<Double>();

    public int distinctAverages(int[] nums) {
        int nlen = nums.length;
        List<Integer> list = new LinkedList<>();
        for (int i = 0; i < nlen; i++) {
            list.add(nums[i]);
        }

        int max;
        int min;
        double avg;
        Collections.sort(list);

        while(list.size() > 0) {
            max = list.get(list.size() - 1);
            min = list.get(0);

            list.remove(list.size()-1);
            list.remove(0);
            avg = (max+min)*1.0/2;

            set.add(avg);

        }

        return set.size();
    }
}

看了题解，发现自己的思路还有很大的优化空间。题解结合了双指针，以及所谓的删除也没必要真的删去，用双指针维护一段有效区间即可。avg也没必要切切实实求出来，因为题干要求的是求不同平均值的数目，数目从set的长度就可以体现。因此，如果两数的和相同平均值就会相同，没必要把平均值的具体答案求出。

这样算法的效率大大提升。

class Solution {
    public int distinctAverages(int[] nums) {
        Arrays.sort(nums);
        Set<Integer> seen = new HashSet<Integer>();
        for (int i = 0, j = nums.length - 1; i < j; ++i, --j) {
            seen.add(nums[i] + nums[j]);
        }
        return seen.size();
    }
}