跳转至

数组总结

总结

数组总结补充参考

https://programmercarl.com/%E6%95%B0%E7%BB%84%E6%80%BB%E7%BB%93%E7%AF%87.html#%E6%80%BB%E7%BB%93

数组的双指针法

同侧双指针

对应题目

  • 27
  • 209

同侧双指针:指指针slowIndex和fastIndex都从左到右遍历

这类方法通常应用于以下for循环的优化

for(int i = 0; i < nums.size(); i++){
        for(int j = i; j < nums.size(); j++){
            //算法步骤
    }
}

在以上for循环中,先移动j满足题意后,再移动i

移动i的过程重复了移动j的过程

例如:

  • 第一次i=0,假设j到达5满足题意停止
  • 第二次i=1,j要重新从0出发,重新经历[0,5]的过程才能到达新元素nums[6]

重新经历[0,5]这一过程是多余的,可以被优化的,因此我们引入双指针

在双指针中

  • 第一次slowIndex = 0(对应i = 0),fastIndex = 0(对应j = 0), fastIndex到达5满足题意停止
  • 接下来不需要重新经历[0,5]的过程,只需要将slowIndex加一(对应i=1)

模板

for(int fastIndex = 0; i < nums.size(); i++){
        while(//题意){
                slowIndex++;
        }
}
异侧双指针

题目:

  • 977

从数组两边往中间遍历,用于对数组两侧元素依次执行算法操作

int leftIndex = 0, rightIndex = nums.size() - 1;
while(leftIndex <= rightIndex){
        if(nums[leftIndex]满足...){
                /...
                leftIndex++;
        }
        if(nums[rightIndex]满足...){
                /...
                rightIndex--;
        }
}