python双指针例题

双指针是一种常用的算法思想，可以用来解决很多问题，比如数组、链表等数据结构相关的问题。下面是一个双指针的例题：

题目描述：给定一个已经排好序的数组 nums 和一个目标值 target，找出数组中两个数的和等于目标值，并返回这两个数的下标。

示例：输入：nums = [2,7,11,15], target = 9，输出：[0,1]

解释：因为 nums + nums = 2 + 7 = 9，所以返回 [0, 1]。

代码实现：

def twoSum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        if nums[left] + nums[right] == target:
            return [left, right]
        elif nums[left] + nums[right] < target:
            left += 1
        else:
            right -= 1
    return []

相关问题

在蓝桥杯Python编程挑战中，如何通过有效应用数据结构来优化解题过程？请结合具体例题，展示《蓝桥杯Python真题解析：算法挑战与代码实践》中的应用实例。

在蓝桥杯等编程竞赛中，数据结构的灵活应用对于问题的解决至关重要。根据《蓝桥杯Python真题解析：算法挑战与代码实践》中的分析，数据结构不仅仅是编程的基础，更是解决复杂问题的关键工具。以“等差数列”为例，题目要求找出数列中的特定项或数列的性质，如求和。在这里，我们可以使用累加求和的方法来优化计算过程。如果数列项数较多，直接求和的效率可能不高，此时可以使用等差数列求和公式S = n(a1 + an)/2，其中n是项数，a1是首项，an是末项。通过计算首尾两项的平均值乘以项数来获得结果，这种方法比逐项累加要高效得多。再比如“递增三元组”问题，我们可以通过排序加遍历的方式来找出所有满足条件的三元组组合。首先将数组排序，然后固定一个数，用两个指针分别指向该数之后的数组开始和末尾，根据递增的规则移动指针，找出所有可能的组合。这种方法充分利用了数组和指针的数据结构特性，有效地解决了问题。通过这些例题，我们可以看到在实际编程挑战中，如何根据题目的特点选择合适的数据结构，以达到优化解题过程的目的。这本资料不仅对蓝桥杯历年的真题进行了详细解析，还针对每一种数据结构的应用提供了实例，是备战竞赛不可或缺的参考资料。

参考资源链接：[蓝桥杯Python真题解析：算法挑战与代码实践](https://wenku.csdn.net/doc/41adqjcz5f?spm=1055.2569.3001.10343)

求两个集合的交集（单链表） 【例题】集合A和B分别用单链表示，求两个集合交集。

在Python中，如果你有两个单链表表示的集合A和B，并想要找到它们的交集，你可以通过遍历两个链表并比较节点元素来实现。这里是一个简单的步骤：

1. 首先，创建两个指针，`p1` 和 `q1` 分别指向集合A和B的头部。

2. 创建一个新的链表（结果链表），`result`，用于存储交集。

3. 进入一个循环，同时移动这两个指针：
- 如果当前`p1` 和 `q1` 的节点值相等，将该节点添加到结果链表`result`，然后都向前移动一个节点。
- 如果`p1` 或 `q1` 到达了链表尾部，说明另一个链表还没有遇到相同的节点，停止循环。

4. 当循环结束时，`result` 链表就是两个集合的交集。注意，这个过程假设链表的节点没有重复，如果有重复，需要额外处理。

以下是伪代码示例：

def find_intersection(p1, q1):
    result_head = None
    result_tail = None

    while p1 and q1:
        if p1.val == q1.val:
            # 如果找到相同节点，则添加到结果链表
            if not result_head:
                result_head = result_tail = Node(p1.val)
            else:
                result_tail.next = Node(p1.val)
                result_tail = result_tail.next
            p1 = p1.next
            q1 = q1.next
        elif p1.val < q1.val:
            p1 = p1.next
        else:
            q1 = q1.next
            
    return result_head if result_head else None

# 使用时：
A_list = ... # 集合A的单链表
B_list = ... # 集合B的单链表
A_head = A_list.head
B_head = B_list.head
intersection = find_intersection(A_head, B_head)