双指针在数组遍历中的应用

算法是计算机软件的基础，今年打算深入学习一些算法，记录一些算法理论以及最佳实践，希望可以坚持下去。

一、前言

数组是最基础的数据结构之一，数组遍历是基本功，本文目的是深入学习双指针法来对数组遍历以及双指针遍历数组算法的实战。

二、双指针介绍

我们一般遍历数组使用一个下标从前往后遍历就可以实现遍历完数组，这整个过程只需要一个下标。

那么双指针是怎么样呢？ 其实就是使用两个下标对数组进行遍历。

为什么需要双指针呢？ 主要为了弥补一些通过单指针遍历数组解决不了的场景。

比如原地移除数组元素。 下面例子需要原地移除元素里的9，通过双指针可以解决，快指针遍历数组元素值，慢指针记录需要留下的元素。但是单指针解决就麻烦。

再比如反转字符串，我们可以通过首尾双指针，通过两个指针同时往中间遍历，交换元素值实现反转功能。

因此双指针有两种类型，一种是前后双指针也可以叫做快慢双指针，一种是首尾双指针。

快慢双指针用来从前往后遍历数组。

首尾双指针用来由两端往中间遍历数组。

三、双指针实战

罗列下部分可以通过双指针解决的leetcode题目：

27. 移除元素

344. 反转字符串

151.翻转字符串里的单词

第15题. 三数之和

977.有序数组的平方

本文分析下有序数组的平方

我们可以借助首尾双指针解决此题，因为平方后的数一定在两端。这样我们可以遍历最大，次最大，次次最大，最后是平方值最小的。以此类推。

class Solution {
    public int[] sortedSquares(int[] nums) {

        int start = 0; //首指针
        int end = nums.length-1; //尾指针

        int[] result = new int[nums.length];
        int index = nums.length - 1;

        while(start <= end) {
            if(nums[start] * nums[start] > nums[end] * nums[end]) {
                result[index--] = nums[start] * nums[start];
                start++;
            } else {
                result[index--] = nums[end] * nums[end];
                end--;
            }
        }

        return result;

    }
}

leetcode18. 四数之和

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {

        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for(int i=0; i<nums.length; i++) {
            
            int a = nums[i];

            if (nums[i] > 0 && nums[i] > target) {
                return result;
            }

            //需要去重a 2 2 2 2 2 不能用while 死循环了
            if(i > 0 && nums[i-1] == nums[i]) {
                continue;
            }
            
            for(int j = i+1; j<nums.length; j++) {

                int b = nums[j];

                //需要去重b
                if(j > i+1 && nums[j-1] == nums[j]) {
                    continue;
                }

                int left = j+1;
                int right = nums.length-1;

                //System.out.println(k+"==="+l);

                while(right>left) {

                    int c = nums[left];
                    int d = nums[right];

                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];

                    if(sum == target) {
                        List<Integer> subResult = new ArrayList<>();
                        subResult.add(a);
                        subResult.add(b);
                        subResult.add(c);
                        subResult.add(d);
                        result.add(subResult);

                        System.out.println(a+"="+b+"="+c+"="+d);

                        while(right>left && nums[right-1] == nums[right]) {
                            right--;
                        }

                        while(right>left && nums[left+1] == nums[left]) {
                            left++;
                        }

                        left++;
                        right--;
                        
                    } else if(sum > target) {
                         right--; 
                         //System.out.println(k+"="+l);  
                    } else if(sum < target) {
                         left++;
                    }
                }
            }

        }

        return result;

    }
}

四数之和这道题通过双指针法从两端往中间来遍历c,d两个元素。

15. 三数之和

class Solution {
    //思路 定义一个固定节点 两个起始节点 移动起始节点确定有没有等于0的情况
    public List<List<Integer>> threeSum(int[] nums) {

        int size = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        for(int i =0; i<size; i++) {

            if(nums[i] >0) {
                return result;
            }
            //去重
            if(i>0 && nums[i] == nums[i-1]) {
                continue;
            }

            int start = i+1;
            int end = size-1;

            while(start < end) {
                
                int r = (nums[start] + nums[end] + nums[i]);
                if(r == 0) {
                    //找到了符合和等于0的，记录下来
                    List<Integer> subResult = new ArrayList<>();
                    subResult.add(nums[i]);
                    subResult.add(nums[start]);
                    subResult.add(nums[end]);
                    result.add(subResult);
                    //去重复
                    while(start< end && nums[start] == nums[start+1]) {
                        start = start +1;
                    }
                    //去除重复
                    while(start < end && nums[end] == nums[end-1]) {
                        end = end-1;
                    }
                    start++;
                    end--;
                    continue;
                } 
                //和大于0，右边的数太大，因此右边的索引要往左移
                if( r > 0) {
                    end--;
                    continue;
                }
                //和小于0，左边的数太小，因此左边的索引往右移
                if( r < 0) {
                   start++;
                }
            }
        }
        return result;
    }
}

三数之和和四数之和是一样的技巧，通过从两端往中间遍历确定b,d的值。

四、总结

本文主要分析了有两种双指针形态，首尾指针和快慢指针。双指针遍历数组可以提高遍历数组算法性能提升。

把双指针算法常见形态和场景记录下来，我相信有输入就需要有输出，希望对以后的编码有帮助。

关注我一起学习算法技巧吧。