【面试高频算法解析】算法练习3 双指针

2024-01-08 22:09:23

前言

本专栏旨在通过分类学习算法,使您能够牢固掌握不同算法的理论要点。通过策略性地练习精选的经典题目,帮助您深度理解每种算法,避免出现刷了很多算法题,还是一知半解的状态


专栏导航

  1. 二分查找
  2. 回溯(Backtracking)
  3. 双指针
  4. 滑动窗口
  5. 深度优先搜索
  6. 广度优先搜索
  7. 贪心算法
  8. 单调队列
  9. 堆(Heap)

算法解析

双指针技术是一种常用的算法策略,它使用两个指针以不同的速度或方向遍历数据结构(通常是线性结构如数组或链表),从而达到解决问题的目的。双指针技术可以帮助我们简化复杂度,减少不必要的运算,尤其是在解决一些与序列相关的问题时非常有效。

双指针通常有以下几种分类:

  1. 快慢指针
    快慢指针通常用于解决链表中的问题,例如检测链表中的循环。快指针每次移动两步,慢指针每次移动一步。如果链表中有循环,则快指针最终会追上慢指针。

  2. 左右指针
    左右指针通常用于有序数组或字符串,开始时一个指向头部(左指针),另一个指向尾部(右指针),然后向中间移动。例如在二分查找、合并两个有序数组或是计算一组数的对数(如两数之和)时会用到。

  3. 滑动窗口(面试中很常见我将另开一篇详细介绍)
    滑动窗口可以看作是一种特殊的双指针,通常用于解决数组/字符串的子区间问题。两个指针共同定义了一个窗口,可以增加或减少窗口的大小以满足特定条件,例如找出满足条件的最长/最短的子数组/子字符串。

双指针技术的优势在于它可以减少时间复杂度。例如,在排序数组中寻找两数之和等于特定值的问题中,暴力解法需要 O(n^2) 的时间复杂度,而使用双指针技术则可以降低到 O(n)。

下面是一个使用双指针(左右指针)解决“两数之和”问题的示例:

def two_sum_sorted(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        current_sum = numbers[left] + numbers[right]
        if current_sum == target:
            return [left + 1, right + 1]  # 返回的是位置,不是索引
        elif current_sum < target:
            left += 1  # 和太小,移动左指针
        else:
            right -= 1  # 和太大,移动右指针
    return [-1, -1]  # 如果没有找到,返回[-1, -1]

在这个函数中,左指针从数组的开始位置向右移动,右指针从数组的结束位置向左移动,直到找到两数之和等于目标值或左右指针相遇。通过这种方式,我们只需要遍历数组一次,从而提高了算法的效率。


实战练习

寻找重复数

给定一个包含 n + 1 个整数的数组 nums ,其数字都在 [1, n] 范围内(包括 1 和 n),可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ,返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1:
输入:nums = [1,3,4,2,2]
输出:2

示例 2:
输入:nums = [3,1,3,4,2]
输出:3

提示:
1 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n
nums 中 只有一个整数 出现 两次或多次 ,其余整数均只出现 一次

进阶:
如何证明 nums 中至少存在一个重复的数字?
你可以设计一个线性级时间复杂度 O(n) 的解决方案吗?

官方题解


三数之和

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意: 答案中不可以包含重复的三元组。

示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。

示例 2:
输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。

示例 3:
输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 。

官方题解


删除排序链表中的重复元素II

给定一个已排序的链表的头 head , 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回 已排序的链表 。

示例 1:
请添加图片描述

输入:head = [1,2,3,3,4,4,5]
输出:[1,2,5]

示例 2:
请添加图片描述

输入:head = [1,1,1,2,3]
输出:[2,3]

提示:
链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序 排列

官方题解

文章来源:https://blog.csdn.net/sinat_41883985/article/details/135346712
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。