587. Two Sum - Unique pairs

LintCode 炼码

排序之后利用对向双指针。

设置visited来去重 => 总是TLE，想了下改成了跟前值比较就行了。

class Solution:
    """
    @param nums: an array of integer
    @param target: An integer
    @return: An integer
    """
    def twoSum6(self, nums, target):
        if len(nums) < 2: return 0
        
        res = 0
        prev = float('inf')
        nums.sort()
        
        l, r = 0, len(nums)-1
        while l < r:
            if nums[l] + nums[r] == target and nums[l] != prev:
                res += 1
                prev = nums[l]
                l += 1 
                r -= 1 
            elif nums[l] + nums[r] > target:
                r -= 1 
            else:
                l += 1
        
        return res

更新一个@肖 启发的向后看去重写法。

注意点是：n个重复元素向后看去重，那只能在最后一个元素那里计数，所以要先执行重复判断，最后再进行结果计数。

class Solution:
    """
    @param nums: an array of integer
    @param target: An integer
    @return: An integer
    """
    def twoSum6(self, nums, target):
        if len(nums) < 2: return 0
        
        res = 0
        nums.sort()
        
        l, r = 0, len(nums)-1
        while l < r:
            if nums[l] + nums[r] > target:
                r -= 1 
            elif nums[l] + nums[r] < target:
                l += 1 
            else:
                while l < r and nums[l] == nums[l+1]:
                    l += 1
                res += 1
                l += 1 
                r -= 1 
        return res