首页 > 其他分享 >leetcode-15. 三数之和 - 双指针问题

leetcode-15. 三数之和 - 双指针问题

时间:2024-03-06 14:44:05浏览次数:19  
标签:right 15 nums 三数 leetcode res 指针 ptr left

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        mem = set()
        for i in range(len(nums)):
            if nums[i] > 0:
                break
            if i > 0 and nums[i-1] == nums[i]:
                continue
            left_ptr, right_ptr = i + 1, len(nums) - 1
            while left_ptr < right_ptr:
                if nums[i] + nums[left_ptr] > 0:
                    break
                tmp_res = nums[i] + nums[left_ptr] + nums[right_ptr]
                if tmp_res == 0 and (nums[i], nums[left_ptr], nums[right_ptr]) not in mem:
                    res.append([nums[i], nums[left_ptr], nums[right_ptr]])
                    mem.add((nums[i], nums[left_ptr], nums[right_ptr]))
                    while left_ptr < right_ptr and nums[left_ptr] == nums[left_ptr+1]:
                        left_ptr += 1
                    while left_ptr < right_ptr and nums[right_ptr] == nums[right_ptr-1]:
                        right_ptr -= 1
                    left_ptr += 1
                    right_ptr -= 1
                elif tmp_res < 0:
                    left_ptr += 1
                else:
                    right_ptr -= 1
        return res

分析

典型的双指针问题。

如果用暴力搜索需要O(n**3)的时间开销。

如果采用排序+双指针,理论上排序后双指针暴力也是O(n**3),但排序后适当选择指针位置可以剪枝。

剪枝的逻辑有3个。

第一个,最外层nums[i]如果大于0,那么nums[left_ptr]和nums[right_ptr]必然大于0;

第二个,如果nums[i] == nums[i-1],那证明相同的组合已经被搜索过;

第三个,跟第二个类似,如果nums[left_ptr] == nums[left_ptr+1],或者nums[right_ptr] == nums[right_ptr-1],那么证明相同的组合已经被搜索过;

标签:right,15,nums,三数,leetcode,res,指针,ptr,left
From: https://www.cnblogs.com/bjfu-vth/p/18056579

相关文章

  • LeetCode75 1768.交替合并字符串
    1768.交替合并字符串https://leetcode.cn/problems/merge-strings-alternately/description/?envType=study-plan-v2&envId=leetcode-75publicStringmergeAlternately(Stringword1,Stringword2){intlen1=word1.length();intlen2=word2.length()......
  • leetcode--901. 股票价格跨度(单调栈)
    记录10:002024-3-6https://leetcode.cn/problems/online-stock-span/维护一个单调递减的栈s,并且也要一个记录个数的栈count每次来一个数据,这个数据如果比s栈顶数据小,就直接放入s,并在count中记录下它的个数1如果这个数据比s栈顶数据大,就需要弹出s和count的top,来保证s是递减的......
  • 文心一言 VS 讯飞星火 VS chatgpt (208)-- 算法导论15.4 5题
    五、设计一个O($n^2$)时间的算法,求一个n个数的序列的最长单调递增子序列。要写代码的时候,请用go语言。文心一言,抛panic:在Go语言中设计一个O(n^2)时间复杂度的算法来求一个n个数的序列的最长单调递增子序列(LongestIncreasingSubsequence,LIS)可以使用动态规划的方法......
  • leetcode--1976. 到达目的地的方案数(最短路)
    记录12:052024-3-5https://leetcode.cn/problems/number-of-ways-to-arrive-at-destination/通过最短路找到从源点到目标点距离,在更新的过程中,对某个点记录下可以达到最短距离的父亲节点,然后从目标点往回dp就可以了(有种逆向拓扑排序的感觉)当然这是不必要的,在更新最短距离的......
  • 聊聊sql优化的15个小技巧(转)
    原文:https://mp.weixin.qq.com/s/DsUrEHdkMvsO7RvnDcKNhg1避免使用select*很多时候,我们写sql语句时,为了方便,喜欢直接使用select*,一次性查出表中所有列的数据。反例:select*fromuserwhereid=1;在实际业务场景中,可能我们真正需要使用的只有其中一两列。查了很多数据,但......
  • CodeForces 1540D Inverse Inversions
    洛谷传送门CF传送门小清新题。首先容易发现每个合法的\(b\)唯一对应一个排列,大概就是每个时刻排列元素的相对顺序,然后插入到相应的位置。但是这样太麻烦了。发现题目只要求求单点的\(p\)值。这应该有更简单的方法。考虑令\(b_i\getsi-b_i\)表示\(p_i\)在前缀\(......
  • 15. 创建卡牌布局
    在项目中添加CardLayoutManager代码如下usingSystem.Collections.Generic;usingUnityEngine;publicclassCardLayoutManager:MonoBehaviour{publicboolisHorizontal;//摄像机的大小是6,分辨率是1920x1080,也就是说摄像机可以看到(-10.7,-6)~(10.7,6)的物体......
  • 代码随想录算法训练营day13 | leetcode 239. 滑动窗口最大值、347. 前 K 个高频元素
    目录题目链接:239.滑动窗口最大值-困难题目链接:347.前K个高频元素-中等题目链接:239.滑动窗口最大值-困难题目描述:给你一个整数数组nums,有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。......
  • 15_依赖注入和控制反转
    依赖注入和控制反转在.NET中,依赖注入(DI)是一种技术,用于实现控制反转(IoC),它允许将类的依赖关系通过构造函数、方法或属性来注入。这样可以提高代码的模块化和可测试性。IServiceCollection是一个服务集合,用于注册应用程序中的服务和组件。这些服务之后可以通过IServic......
  • p7915-solution
    P7915Solutionlink考虑枚举第一个操作选L还是R。这样原序列就被分为了两个栈,用四个指针\(p1,p2,p3,p4\)分别指向这两个栈的栈顶栈底。感性理解一下,某一个栈的栈顶\(x\)可以被pop当且仅当某一个栈的栈底等于\(x\)。于是直接dfs,每次优先选L,同时确定第\(2n-i+1\)......