1.题目描述

给定一个有序数组, 求它的元素的绝对值个数. 如数组[-3, -1, 0, 0, 2, 3, 5], 返回5.

2.解题思路

这个题，利用Hashset进行顺序遍历，最后返回set的size()就可以，但是时间复杂度是o(n)，要优化算法，我们就需要这样一个思路，看到有序数组，我们首先需要想到二分查找或者双指针的方式。

本题中使用双指针，一个在数组头部，一个在数组尾部，然后两个指针朝两个方向向中间夹逼。我们利用双指针所指向的数的加和做判断，那么它们的加和只有三种情况。

因为数组是排好序的，所以

（1）左右加和大于0，说明尾指针指向的数比头指针指向的数要大，此时我们将尾指针向前移动一位，并将计数加1.

（2）左右加和小于0，说明头指针指向的数是负数，且绝对值比尾指针指向的数要大，此时将头指针向后移动一位，并将计数加1.

（3）左右加和等于0，说明头指针指向的数是负数，且绝对值和尾指针指向的数相等，此时我们需要将首尾指针都向中间推进一位，并将计数加1.

（4）另外，当首尾指针相遇的时候，此时已经退出了循环，首尾指针指向同一个数，此时我们的计数需要再加1.

注意：数组中含有重复值的情况，要在比较之前跳过重复值，并且注意去重时指针移动的边界，不可以移动到首尾！

public int countDistinctAbs(int[] nums){ if(nums==null||nums.length==0){ return -1; } int i=0; int j=nums.length-1; int count=0; while(i<j){ if(i<nums.length-1&&nums[i]==nums[i+1]){ i++; } if(j>1&&nums[j]==nums[j-1]){ j--; } if(nums[i]+nums[j]==0){ i++; j--; count++; }else if(nums[i]+nums[j]>0){ j--; count++; }else if(nums[i]+nums[j]<0){ i++; count++; } } if(i==j){ count++; } return count; }

相似题目 有序数组每个数平方后，不同数字的个数？O(n):https://blog.csdn.net/qq_28468707/article/details/103672590