【2025-02-05】LeetCode刷题——基础算法：相向双指针

用户11029137

发布于 2025-02-06 08:16:36

2260

文章被收录于专栏：编程学习编程学习

一，题目汇总

●视频题目题号： 167，15 ●课后作业题号： 2824，16，18，611

二，视频题目

1，167.两数之和

暴力算法时间复杂度：O(

n^2

) 优化思路：设置两个相向的指针，利用数组是排好序这一特点，减少对中间数字的比较如：2.3.4.6.8，找9，若2+8 > 9，则代表8+2后面任何数>9，一次比较获得了O(n)个信息

●题解：

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left = 0
        right = len(numbers) - 1 
        while left < right:
            s = numbers[left] + numbers[right]
            if s == target:
                break
            elif s > target:
                right -= 1
            else:
                left += 1
        return [left+1, right+1] # 注意这里数组下边从1开始

2，15.三数之和

●题解：对一个数进行枚举，另外两个数进行相加比较答案不重复：当数重复时：跳过

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans = []
        # 从第一个数枚举到倒数第三个数
        for i in range(len(nums)-2):
            # 跳过重复
            if i > 0 and nums[i] == nums[i-1]:
                continue
            j = i + 1
            k = len(nums) - 1
            while j < k:
                s = nums[i] + nums[j] + nums[k]
                if s < 0:
                    j += 1
                elif s > 0:
                    k -= 1
                else:
                    ans.append([nums[i],nums[j],nums[k]])
                    j += 1 # 让双向指针都向内移动一格，继续找其他组合解
                    while j < k and nums[j] == nums[j-1]:
                        j += 1
                    k -= 1
                    while j < k and nums[k] == nums[k+1]:
                        k -= 1
        return ans

三，课后作业

1，2824.统计和小于目标的下标对数目

●题解：

class Solution:
    def countPairs(self, nums: List[int], target: int) -> int:
        nums.sort()
        left = ans = 0
        right = len(nums) - 1
        while left < right:
            if nums[left] + nums[right] >= target:
                right -= 1
            else:
                ans += right - left
                left += 1
        return ans

2，16.最接近的三数之和

●题解：

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        min_diff = inf
        for i in range(len(nums)-2):
            j = i + 1
            k = len(nums) - 1
            while j < k:
                s = nums[i] + nums[j] + nums[k]
                if s == target:
                    return s
                elif s > target:
                    if s - target < min_diff:
                        min_diff = s - target
                        ans = s
                    k -= 1
                else:
                    if target - s <  min_diff:
                        min_diff = target - s
                        ans = s
                    j += 1
        return ans

3，18.四数之和

题解：

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        ans = []
        for i in range(len(nums)-3):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            for j in range(i+1, len(nums)-2):
                if j > i+1 and nums[j] == nums[j-1]:
                    continue
                n = j + 1
                m = len(nums) - 1
                while n < m:
                    s = nums[i] + nums[j] + nums[n] + nums[m]
                    if s < target:
                        n += 1
                    elif s > target:
                        m -= 1
                    else:
                        ans.append([nums[i], nums[j], nums[n], nums[m]])
                        n += 1
                        while n < m and nums[n] == nums[n-1]:
                            n += 1
                        m -= 1
                        while n < m and nums[m] == nums [m+1]:
                            m -= 1
        return ans

4，611.有效三角形的个数

题解：固定最大边解法：

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        ans = 0
        # 固定最大边
        for i in range(2,len(nums)):
            right = i - 1
            left = 0
            while left < right:
                if nums[left] + nums[right] > nums[i]:
                    ans += right - left
                    right -= 1
                else:
                    left += 1
        return ans

首先，双指针问题本质上就是一个“条件判定值”的问题，三数问题本质上其实就是一个将二数问题的判定值挪为我们所选的定点i的值的过程。简单来说，我们有一个target，通过和target比较，来决定left指针和right指针的移动方向在这个有效三角形的个数这个问题里：假设，三角形的三条边从小到大依次是a，b，c 最大边解法：定最大边c，使得a和b满足a+b>c 如果我们让数组从小到大排序，即直接使用sort()，则很清晰的： a左移可以使a+b变大，更接近c，b右移可以使a+b变小，即两指针相向移动时可以从不同方向接近c