数据结构与算法实例详解--数学、数论、数组、双指针 ， 三数一双组合

数学数论

数学数论是研究整数及其性质的数学分支。在计算机科学中，数论常常用于算法分析、密码学和图论等领域。数论的基本概念包括：

1. 素数：只能被1和自身整除的自然数，例如2、3、5、7等。
2. 最大公约数（GCD）：一个整数集合的公因数中最大的那个。例如，12和18的最大公约数是6。
3. 最小公倍数（LCM）：能够同时被给定整数集合整除的最小正整数。
4. 模运算：对于整数a和正整数m，模m的结果是a与m的商的余数，表示为a mod m。

数论的算法常常用到，例如使用欧几里得算法计算最大公约数，或在密码学中大数的分解和模运算。

数组

数组是一种线性数据结构，用于存储固定大小的元素集合。每个元素在数组中有一个对应的索引，可以通过索引快速访问。数组常见的操作包括：

1. 访问：根据索引获取数组中的元素，时间复杂度为O(1)。
2. 插入：将元素插入数组中的特定位置，时间复杂度最坏为O(n)。
3. 删除：移除数组中的元素，时间复杂度最坏为O(n)。
4. 遍历：依次访问数组中的每个元素，时间复杂度为O(n)。

数组在实际编程中非常常用，特别是在需要快速随机访问的应用中。

双指针

双指针是一种经典的算法技巧，常用于数组和链表等数据结构中的问题解决。顾名思义，双指针涉及两个指针，它们可以从不同方向或位置向中间移动，通常用于寻找特定元素、配对元素或解决子数组问题。

双指针的常见应用场景包括：

1. 寻找特定元素：如在排序数组中寻找两个数的和为目标值。
2. 回文字符串检查：使用左右指针检查是否为回文。
3. 合并两个有序数组：通过一个指针遍历第一个数组，另一个指针遍历第二个数组，从而高效合并。
4. 滑动窗口问题：例如查找最长无重复子字符串，使用双指针动态维护窗口边界。

双指针技术通常能降低算法的复杂度，从而提高程序的执行效率。

话不多说，直接上题:

3115.质数的最大距离【中等】
题目：
给你一个整数数组 nums。

返回两个（不一定不同的）质数在 nums 中 下标 的 最大距离。

示例 1：

输入： nums = [4,2,9,5,3]

输出： 3

解释： nums[1]、nums[3] 和 nums[4] 是质数。因此答案是 |4 - 1| = 3。

示例 2：

输入： nums = [4,8,2,8]

输出： 0

解释： nums[2] 是质数。因为只有一个质数，所以答案是 |2 - 2| = 0。

提示：

1 <= nums.length <= 3 * 10**5
1 <= nums[i] <= 100
输入保证 nums 中至少有一个质数。
分析问题：
思路一：        
        题目难度适中，主要思路是利用双指针，头指针从下标0开始往后遍历，尾指针从下标n-1开始往前遍历，先走头指针，碰到质数时指针停下；尾指针开始运动，碰到质数时结束。

        不知道要循环多少次所以用while循环来写，但是在写循环之前要先写判断是否是质数的函数pan。但是需要注意的是 1 不是质数。

如果头指针和尾指针重合，则说明只有一个质数。返回0即可。
如果头指针和尾指针不重合，则直接返回 ed-st 即可。

思路二：
         因为这道题的数据量只有1-100这个区间，所以我们可以直接写出来100以内的所有质数，这样可以直接取，大大减小复杂度，具体思路如下：

        首先定义了一个包含一些质数的集合prime。然后获取输入列表nums的长度n，并初始化两个指针i和j，分别指向列表的开头和结尾。

        接下来，通过一个循环从列表开头开始，找到第一个在prime集合中的数，找到后停止循环，此时i指向该数。然后通过另一个循环从列表结尾开始，找到第一个在prime集合中的数，找到后停止循环，此时j指向该数。

        最后，计算j和i的差值并返回，这个差值就是列表中两个质数的索引距离。

代码实现：
思路一代码实现： 

class Solution:
    def maximumPrimeDifference(self, nums: List[int]) -> int:
        n=len(nums)
        def pan(n:int):
            if n==1: return False
            if n in [2,3]: return True
            for i in range(2,int(n**0.5)+2):
                if n%i==0: return False
            return True
        st,ed=0,n-1
        while st<=ed:
            while  not pan(nums[st]) and st<=ed:
                st+=1
            while not pan(nums[ed]) and st<=ed:
                ed-=1
            if st==ed : return 0
            return ed-st

思路二代码实现：

class Solution:
    def maximumPrimeDifference(self, nums: List[int]) -> int:
        prime = set([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97])
        n = len(nums)
        i, j = 0, n - 1
        while i < n:
            if nums[i] in prime: break
            i += 1
        while j >= 0:
            if nums[j] in prime: break
            j -= 1
        return j - i

总结：
代码详解：
首先获取列表的长度n。
定义了一个函数pan，用于判断一个数是否为质数。如果数为1，则返回False；如果数为2或3，则返回True；对于其他数，从2到该数的平方根加1进行遍历，如果能被整除，则返回False，否则返回True。
然后通过两个指针st和ed分别从列表的两端向中间遍历。在遍历过程中，跳过不是质数的数，直到找到两个都是质数的数。
如果st和ed相等，说明没有找到两个不同的质数，返回0。
否则，返回ed - st。
考点：
质数的判断方法。
双指针遍历列表的技巧。
收获：
加深了对质数判断的理解和实现。
掌握了通过双指针遍历列表来解决问题的方法。
提高了对问题的分析和解决能力，学会如何根据题目要求设计合适的算法。

“既然我无法停留，那么就飞到我再也不能飞的那一天吧。”——《シ舀シ舀》