C程序 双指针技术

C程序 双指针技术的完整使用攻略

双指针技术是C语言中常用的一种编程技巧，它通过利用两个指针的相对位置关系，实现快速查找、合并、移动等操作。下面详细讲解一下如何在C程序中使用双指针技术。

1. 双指针技术概述

双指针技术常用于数组操作、链表操作等场景。在使用双指针技术时，我们需要定义两个指针变量p和q，分别指向数组或链表中的元素。p和q可以指向同一个元素，也可以分别指向不同的元素。

双指针技术主要包括以下几种用法：

• 快慢指针法：通过定义两个指针p和q，其中p的移动速度快于q的移动速度，可以实现快速查找、删除等操作。
• 左右指针法：通过定义两个指针left和right，分别从两端开始移动，可以实现数组元素的倒序排列等操作。
• 对撞指针法：通过定义两个指针p和q，其中p从左端开始移动，q从右端开始移动，可以实现查找两数之和、查找回文串等操作。
• 滑动窗口法：通过定义两个指针left和right，分别指向窗口的左右端点，可以实现查找最长不重复子串等操作。

2. 示例说明

2.1 快慢指针法示例

快慢指针法常用于链表操作，下面是一个示例代码，实现删除链表中的重复元素：

struct ListNode* deleteDuplicates(struct ListNode* head){
    if (head == NULL) return head;
    struct ListNode *p = head, *q = head->next;
    while (q) {
        if (p->val == q->val) {
            p->next = q->next;
            free(q);
            q = p->next;
        } else {
            p = p->next;
            q = q->next;
        }
    }
    return head;
}

在这个示例中，我们定义了一个快指针q和一个慢指针p，p初始化为链表头结点head，q初始化为head的下一个结点。然后依次遍历整个链表，如果p和q指向的元素值相同，就删除q指向的结点；否则就让p和q都向后移动一位。最后返回链表头结点即可。

2.2 对撞指针法示例

对撞指针法常用于数组操作，下面是一个示例代码，实现查找两数之和等于给定值的位置：

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    *returnSize = 2;
    int* res = malloc(sizeof(int) * (*returnSize));
    int left = 0, right = numsSize - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            res[0] = left + 1;
            res[1] = right + 1;
            return res;
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return res;
}

在这个示例中，我们定义了两个指针left和right，分别从数组的左端和右端开始移动，当left和right指向的元素之和等于给定的目标值时，就返回left和right的位置。如果元素之和小于目标值，就让left向右移动一位；如果元素之和大于目标值，就让right向左移动一位。最后返回left和right的位置即可。

3. 总结

双指针技术是C语言中一种常用的编程技巧，常用于数组操作、链表操作等场景。它的主要优点是可以减少时间复杂度，提高代码效率。在使用双指针技术时，我们需要注意指针的取值范围、相对位置关系的变化等。希望本篇文章能够对大家学习双指针技术有所帮助。