中等难度-双指针

来源于leetcode题库11,15,75,287

11.盛最多水的容器

题目描述
- 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
  说明：你不能倾斜容器，且 n 的值至少为 2。
示例

image.png
题解
- 来自于题解区大佬krahets，如有侵扰烦请联系删除

class Solution:
    def maxArea(self, height: List[int]) -> int:
        '''
        双指针i,j分别位于两端，根据规则移动指针，更新最大值res
        每次移动将两指针所在位置的短板向内收一格
        因为面积是由短板决定的，不论短板移动还是长板移动j-i都会缩小1
        但是短板内收一格后，min(height[i],height[j])可能会变大或不变
        而长板内收一格后，min(height[i],height[j])只可能变小或不变
        所以短板内收一格不会错过最大面积
        '''
        # i，j为双指针下标，res初始值为0
        i, j, res = 0, len(height) - 1, 0
        #只要双指针没有相交
        while i < j:
            # 面积由短板决定，所以面积=min(height[i],height[j]) * (j-i)
            if height[i] < height[j]:
                res = max(res, height[i] * (j - i))
                i += 1 # 内收短板
            else:
                res = max(res, height[j] * (j - i))
                j -= 1 # 内收短板
        return res

15.三数之和

题目描述
- 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
示例

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

题解
- 题解来源于题解去大佬krahets

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        '''
        先将nums从小到大进行排序
        设定三个指针：
            固定最小数字的指针k
            指针i,j分别位于(k,len(nums))的两端
        '''
        nums.sort()
        res, k = [], 0
        for k in range(len(nums) - 2):
            # 数组是有序的，如果第一个数字大于0则直接退出
            if nums[k] > 0: 
                break 
            # 如果nums[k] == nums[k-1]则跳过此元素，避免重复元素
            if k > 0 and nums[k] == nums[k - 1]: 
                continue 
            # i，j分别位于k-len(nums)的两端
            i, j = k + 1, len(nums) - 1
            while i < j: # 循环啊
                s = nums[k] + nums[i] + nums[j]
                # 如果s<0,则将i+=1使总和变大
                if s < 0:
                    i += 1
                    # 避免重复元素
                    while i < j and nums[i] == nums[i - 1]: 
                        i += 1
                # 如果s>0,则j-=1使总和减小
                elif s > 0:
                    j -= 1
                    # 避免重复元素
                    while i < j and nums[j] == nums[j + 1]: 
                        j -= 1
                else:
                    #如果s=0，记录k,i,j
                    res.append([nums[k], nums[i], nums[j]])
                    # i+1,j-1，继续寻找并避免重复元素
                    i += 1
                    j -= 1
                    while i < j and nums[i] == nums[i - 1]: i += 1
                    while i < j and nums[j] == nums[j + 1]: j -= 1
        return res

75.颜色分类

题目描述
- 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
  此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
示例

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

题解

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        p0, curr, p2 = 0, 0, len(nums) - 1
        while curr <= p2:
            if nums[curr] == 0: # 为0，做出决策
                nums[p0], nums[curr] = nums[curr], nums[p0]
                p0 += 1
                curr += 1
            elif nums[curr] == 2:   # 为2，做出决策
                nums[p2], nums[curr] = nums[curr], nums[p2]
                p2 -= 1
            else:                   # 为1，做出决策
                curr += 1

287.寻找重复数

题目描述
- 给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例

略

题解
- 题解来源于题解区大佬liweiwei1419

#使用二分查找法
from typing import List
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        size = len(nums)
        left = 1
        right = size - 1

        while left < right:
            mid = left + (right - left) // 2

            cnt = 0
            for num in nums:
                if num <= mid:
                    cnt += 1
            # 根据抽屉原理，小于等于 4 的数的个数如果严格大于 4 个，
            # 此时重复元素一定出现在 [1, 4] 区间里

            if cnt > mid:
                # 重复的元素一定出现在 [left, mid] 区间里
                right = mid
            else:
                # if 分析正确了以后，else 搜索的区间就是 if 的反面
                # [mid + 1, right]
                left = mid + 1
        return left