Description
Given an array of integers, find how many unique pairs
in the array such that their sum is equal to a specific target number. Please return the number of pairs.
(http://www.lintcode.com/problem/two-sum-unique-pairs/)
Solution
class Solution:
"""
@param nums: an array of integer
@param target: An integer
@return: An integer
"""
def twoSum6(self, nums, target):
if not nums or len(nums) < 2:
return 0
#先对数组进行sort,之后前后一起遍历,主义跳过重复的元素
#小于左+1,大于右-1至l==r
nums.sort()
count = 0
left, right = 0, len(nums) - 1
while left < right:
if nums[left] + nums[right] == target:
count, left, right = count + 1, left + 1, right - 1
while left < right and nums[right] == nums[right + 1]:
right -= 1
while left < right and nums[left] == nums[left - 1]:
left += 1
elif nums[left] + nums[right] > target:
right -= 1
else:
left += 1
return count
网友评论