当前位置：首页 > article >正文

双指针的用法以及示例

article 2024/9/21 18:48:18

当然可以！双指针（Two Pointers）是一种常用的算法技巧，特别适用于处理数组或链表等线性数据结构的问题。以下是双指针用法的总结：

双指针用法总结

基本概念：
- 双指针技术使用两个指针在数据结构上进行遍历，通常用于解决与子数组、子序列、区间等相关的问题。
常见类型：
- 滑动窗口：用于查找满足特定条件的子数组或子串，通常涉及到动态调整两个指针的位置。
- 对撞指针：用于从两端向中间逼近，常用于排序数组的查找、配对等问题。
滑动窗口的步骤：
- 初始化：设置两个指针（通常是 left 和 right）和一个窗口的状态（如和、长度等）。
- 扩展窗口：移动 right 指针，增加窗口的大小，更新窗口状态。
- 收缩窗口：当窗口状态不满足条件时，移动 left 指针，减小窗口的大小，直到满足条件。
- 记录结果：在每次满足条件时，记录当前窗口的状态（如长度、下标等）。
对撞指针的步骤：
- 初始化：设置两个指针，通常一个指向数组的开始，另一个指向数组的结束。
- 比较和移动：根据条件比较两个指针指向的元素，决定移动哪个指针，直到两个指针相遇。
应用场景：
- 查找和不超过某个值的最大子数组。
- 查找两个数的和等于目标值。
- 反转字符串或数组。
- 处理有序数组的合并、去重等问题。

示例代码

假如说给你一个数组[8, 4, 6, 3, 1, 6, 7]，找出不大于10的连续子数组的最大长度

def max_subarray_length(nums, threshold):  
    l = 0  
    window_sum = 0  
    max_length = 0  

    for r in range(len(nums)):  
        window_sum += nums[r]  

        while window_sum > threshold and l <= r:  
            window_sum -= nums[l]  
            l += 1  

        # 更新最大长度  
        if window_sum <= threshold:  
            max_length = max(max_length, r - l + 1)  

    return max_length  

# 示例数组  
nums = [8, 4, 6, 3, 1, 6, 7]  
threshold = 10  
result = max_subarray_length(nums, threshold)  
print("Maximum length of subarray with sum not greater than 10:", result)

在这里插入图片描述
假如说给你一个数组[8, 4, 6, 3, 1, 6, 7]，找出不大于10的连续子数组

def find_subarrays(nums, threshold):  
    l = 0  
    window_sum = 0  
    valid_subarrays = []  

    for r in range(len(nums)):  
        window_sum += nums[r]  

        while window_sum > threshold and l <= r:  
            window_sum -= nums[l]  
            l += 1  

        # 在此记录所有满足条件的子数组  
        for i in range(l, r + 1):  
            valid_subarrays.append(nums[i:r + 1])  

    return valid_subarrays  

# 示例数组  
nums = [8, 4, 6, 3, 1, 6, 7]  
threshold = 10  
result = find_subarrays(nums, threshold)  
print("Continuous subarrays with sum not greater than 10:")  
for subarray in result:  
    print(subarray)

在这里插入图片描述
假如说给你一个数组[8, 4, 6, 3, 1, 6, 7]，找出不大于10的最大连续子数组以及最大长度

def max_subarray_length_and_all_indices(nums, threshold):  
    l = 0  
    window_sum = 0  
    max_length = 0  
    valid_subarrays = []  

    for r in range(len(nums)):  
        window_sum += nums[r]  

        while window_sum > threshold and l <= r:  
            window_sum -= nums[l]  
            l += 1  

        current_length = r - l + 1  
        if window_sum <= threshold:  
            if current_length > max_length:  
                max_length = current_length  
                valid_subarrays = [(l, r)]  
            elif current_length == max_length:  
                valid_subarrays.append((l, r))  

    return max_length, valid_subarrays  

# 示例数组  
nums = [8, 4, 6, 3, 1, 6, 7]  
threshold = 10  
result_length, result_indices = max_subarray_length_and_all_indices(nums, threshold)  
print("Maximum length of subarray with sum not greater than 10:", result_length)  
print("Indices of all maximum subarrays:", result_indices)