双指针技巧套路-数组

部分重复题目请参考：原地修改数组 (opens new window)

题目：

167. 两数之和 II - 输入有序数组 (opens new window)

344. 反转字符串 (opens new window)

之前我们是在数组中使用快慢指针来解决一些问题，这次我们把快慢指针充当索引，可以用来解决一些关于原地修改数组的问题。如果使用左右指针可以解决一下在二分查找基础上进行变化的数组问题。

二分查找的模板：

int binarySearch(int[] nums, int target) {
    // 一左一右两个指针相向而行
    int left = 0, right = nums.length - 1;
    while(left <= right) {
        int mid = (right + left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; 
        else if (nums[mid] > target)
            right = mid - 1;
    }
    return -1;
}

两数之和II

题目：

思想：

因为题目已经说明了非递减顺序排列，那么数组是增序，且只对应唯一的答案。利用双指针左右依次往中间走，计算每次左右指针对应的元素之和，如果小于目标值，说明左边的不够大，左指针向右移动。如果大于目标值，说明

右边的太大，右指针往左移动。

代码：

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        if(numbers.length == 0) {
            return null;
        }
        int left = 0, right = numbers.length - 1;
        while(left < right) {
            int sum = numbers[left] + numbers[right];
            if(sum == target) {
                return new int[]{left + 1, right + 1};
            }
            else if(sum < target) {
                left++;
            } 
            else if(sum > target) {
                right--;
            }

        }
        return null;
    }
}

反转数组

题目：

思想：

这个相当于数组的反转了，除了使用语言自带的函数，我们利用左右指针也可以较快完成。

代码：

class Solution {
    public void reverseString(char[] s) {
        // 一左一右两个指针相向而行
        int left = 0, right = s.length - 1;
        while (left < right) {
            // 交换 s[left] 和 s[right]
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }
}

参考

双指针技巧秒杀七道数组题目 (opens new window)