美文网首页
Lint ** Two Sum II

Lint ** Two Sum II

作者: Mree111 | 来源:发表于2019-10-09 23:51 被阅读0次

    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
    

    相关文章

      网友评论

          本文标题:Lint ** Two Sum II

          本文链接:https://www.haomeiwen.com/subject/qpoipctx.html