题目

给定一个有序数组arr，其中值可能为正、负、0
返回arr中每个数都平方之后不同的结果有多少种？

一.哈希表

遍历每一个数,如果有不同的,就放入哈希表里
如果哈希表内有的话就跳过

    public static int diff1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        HashSet<Integer> set = new HashSet<>();
        for (int cur : arr) {
            set.add(cur * cur);
        }
        return set.size();
    }

二、双指针

对于比较不同,并且数组是有序的,可以考虑使用双指针
左指针从头出发,右指针从尾部出发
比较两个指针的绝对值,如果不相等,那就记录
绝对值大的指针往中间滑,如果旁边的数与指针的数相等,那就继续滑,直到遇到不相等的数
如果两个指针的绝对值都相等,那就两个指针一起滑,直到遇到不同的数

代码

    public static int diff2(int[] arr) {
        int N = arr.length;
        int L = 0;
        int R = N - 1;
        int count = 0;
        int leftAbs = 0;
        int rightAbs = 0;
        while (L <= R) {
            count++;
            leftAbs = Math.abs(arr[L]);
            rightAbs = Math.abs(arr[R]);
            if (leftAbs < rightAbs) {
                while (R >= 0 && Math.abs(arr[R]) == rightAbs) {
                    R--;
                }
            } else if (leftAbs > rightAbs) {
                while (L < N && Math.abs(arr[L]) == leftAbs) {
                    L++;
                }
            } else {
                while (L < N && Math.abs(arr[L]) == leftAbs) {
                    L++;
                }
                while (R >= 0 && Math.abs(arr[R]) == rightAbs) {
                    R--;
                }
            }
        }
        return count;
    }

总结

遇到数组找出有多少个不同的数的问题,可以考虑使用双指针法,可以设置两个指针
左指针在头节点出发,右指针从尾出发