题目描述

给你一个有序整数数组，数组中的数可以是正数、负数、零，请实现一个函数，这个函数返回一个整数：返回这个数组所有数的平方值中有多少种不同的取值。举例：
nums = {-1,1,1,1},
那么你应该返回的是：1。因为这个数组所有数的平方取值都是1，只有一种取值。
nums = {-1,0,1,2,3}
你应该返回4，因为nums数组所有元素的平方值一共4种取值：1,0,4,9

方法1

每个都算一次平方，存入hash，去除重复的。时空复杂度O(n)

方法2 双指针

时间复杂度O(n), 空间复杂度O(1)

循环外层，保证左指针不大于右指针一直循环，每次找出一个数，循环完就找完了。
循环内， 左右边找出一个abs的最大值作为锚，两头同时开始数，和锚一样的都去掉。

class Solution(object):
    def getSquareCount(self, nums):
        if (len(nums) == 0):
            return 0
        nums = [abs(x) for x in nums]
        left = 0
        right = len(nums) - 1
        result = 0
        while left <= right:
            anchor = max(nums[left], nums[right])
            while left < len(nums) and nums[left] == anchor:
                left += 1
            while right >= 0 and nums[right] == anchor:
                right -= 1
            result += 1
        return result


if __name__ == '__main__':
    assert 1 == Solution().getSquareCount([-1, 1, 1, 1])
    assert 5 == Solution().getSquareCount([-3, -3, -2, -2, -1, -1, 0, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4])
    assert 4 == Solution().getSquareCount([-1, 0, 1, 2, 3])