C++双指针法

目的

使用双指针思路可以大大降低算法时间复杂度。

实例

题目描述

求一个有序数组中和=8的下标。

解题思路

设置两个不同的指针 ，或者头，或者尾。在一个递增的序列中，根据结果分类，判断指针的下一步应该怎么移动。
结果分类：
a[i]+b[j]==8则i++，j- -都相互靠近;
a[i]+b[j] < 8 ,需要移动指针i ,i++（i与a[i]成正比，增加i即可使结果靠近8）;
a[i]+b[j] > 8 ,需要移动指针j ,j- -（减少j使结果靠近8）。

代码

//在有序数组中求出两个数和为8的数
void TwoPointerEg1(){
    int num[8] = { 1, 2, 3, 4, 5, 6 ,7,8};
    int i = 0, j = 7;
    while (i<j){    // 保证i、j的索引不会重叠
        if (num[i] + num[j] == 8)
        {
            cout << i << "  " << j << endl;
            i++;
            j++;
        }
        else if (num[i] + num[j] > 8)
        {
            j--;//如果两个数相加大于10，所以需要缩小一个数，j--实现递增数组缩小
        }
        else{
            i++;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20