美文网首页
三数之和 - 数组,双指针问题

三数之和 - 数组,双指针问题

作者: RayRaymond | 来源:发表于2020-04-22 22:04 被阅读0次

    15. 三数之和

    给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。
    注意:答案中不可以包含重复的三元组。

    示例:
    给定数组 nums = [-1, 0, 1, 2, -1, -4],
    满足要求的三元组集合为:
    [
    [-1, 0, 1],
    [-1, -1, 2]
    ]

    暴力, 三重遍历

    import copy
    
    class Solution:
        def threeSum(self, nums: List[int]) -> List[List[int]]:
            res = []
            for x in nums:
                xnum = copy.deepcopy(nums)
                xnum.remove(x)
                for y in xnum:
                    ynum = copy.deepcopy(xnum)
                    ynum.remove(y)
                    for z in ynum:
                        if x + y + z == 0:
                            if [x,y,z] in res or [x,z,y] in res or [y,x,z] in res or [y,z,x] in res or [z,x,y] in res or [z,y,x] in res:
                                pass
                            else:
                                res.append([x,y,z])
            return res
    

    双指针法

    遍历排序后数组:

    • 若 nums[i]>0:
      因为已经排序好,所以后面不可能有三个数加和等于 0,直接返回结果。
    • 对于重复元素:
      跳过,避免出现重复解

    令左指针 L=i+1,右指针 R=n-1,当 L<R时,执行循环:
    当 nums[i]+nums[L]+nums[R]==0,执行循环,判断左界和右界是否和下一位置重复,去除重复解。并同时将 L,R 移到下一位置,寻找新的解

    • 若和大于 0,说明 nums[R] 太大,R 左移
    • 若和小于 0,说明 nums[L] 太小,L 右移
    class Solution:
        def threeSum(self, nums: List[int]) -> List[List[int]]:
            nums.sort()
            n = len(nums)
            res = []
            if n < 3 or not nums:
                return []
    
            for i in range(n):
                if(nums[i] > 0):
                    return res
                if(i>0 and nums[i] == nums[i-1]):
                    continue
    
                L = i + 1
                R = n - 1
                while L < R:
                    if nums[i]+nums[L]+nums[R] == 0:
                        res.append([nums[i],nums[L],nums[R]])
                        while L<R and nums[L] == nums[L+1]:
                            L += 1
                        while(L<R and nums[R] == nums[R-1]):
                            R -= 1
                        L += 1
                        R -= 1
                    elif nums[i]+nums[L]+nums[R] > 0:
                        R -= 1
                    else:
                        L += 1
            return res
    

    16. 最接近的三数之和

    给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

    nums = [-1,2,1,-4], target = 1.
    与 target 最接近的三个数的和为 2.
    -1 + 2 + 1 = 2

    对 nums 排序
    双指针法不断计算 sums 和 target 比较:
    如果一致直接返回。
    如果差值比之前存储的小就替换。
    sums 比 target 小,左指针右移,增大左值
    sums 比 target 大,右指针左移,减小右值

    
    class Solution:
        def threeSumClosest(self, nums: List[int], target: int) -> int:
            n = len(nums)
            if not sum or n<3:
                return []
            nums.sort()
            res = float('inf')
            for i in range(n):
                if i>0 and nums[i] == nums[i-1]:
                    continue
                L = i+1
                R = n-1
                while L<R:
                    cur_sum = nums[i] + nums[L] + nums[R]
                    diff = cur_sum - target
                    if diff == 0:
                        return target
                    if abs(diff) < abs(res-target):
                        res = cur_sum
                    if diff < 0:
                        L += 1
                        while L<R and nums[L] == nums[L-1]:
                            L+=1
                    else:
                        R -= 1
                        while L<R and nums[R] == nums[R+1]:
                            R-=1
            return res
    

    相关文章

      网友评论

          本文标题:三数之和 - 数组,双指针问题

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