双指针一般是指利用两个变量，通过在线性的结构上进行遍历来解决某些特定的问题，按照遍历的方式一般多采用：同向遍历，相向遍历两种方式，例如冒泡排序、选择排序、插入排序都是用了两个变量同向遍历来实现，快排则是通过相向遍历来实现。
快慢指针的简单应用
public int removeDuplicates(int[] nums) {
int n = nums.length;
int p1 = 0;
int p2 = 1;
while (p2 < n) {
if (nums[p1] != nums[p2]) {
nums[++p1] = nums[p2];
}
p2++;
}
return p1 + 1;
}
leetcode跳转： 26. 删除有序数组中的重复项
与前一题结合在一起看，就是保留前
X
个相同数字，超过
X
个后，再进行比较，所以快指针逻辑不变，只需要让慢指针在比较时每次往前取两位即可。
public int removeDuplicates(int[] nums) {
int n = nums.length;
if (n <= 2) {
return n;
}
int p1 = 2;
int p2 = 2;
while (p2 < n) {
if (nums[p1 - 2] != nums[p2]) {
nums[p1] = nums[p2];
p1++;
}
p2++;
}
return p1;
}
leetcode跳转： 80. 删除有序数组中的重复项II
public void moveZeroes(int[] nums) {
int zero = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
int t = nums[i];
nums[i] = 0;
nums[zero] = t;
zero++;
}
}
}
leetcode跳转： 283. 移动零
左右指针，相向遍历
public int[] twoSum(int[] numbers, int target) {
int n = numbers.length;
int left = 0;
int right = n - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return new int[]{left + 1, right + 1};
} else if (sum > target) {
right--;
} else {
left++;
}
}
return null;
}
leetCode跳转： 167. 两数之和 II - 输入有序数组
同样是一道左右指针，相向遍历的题，每次移动较短的柱子，盛水最多的容器，即为：间距 * min(left, right)
public int maxArea(int[] height) {
int n = height.length;
int left = 0;
int right = n - 1;
int ans = 0;
while (left < right) {
int min = Math.min(height[left], height[right]);
ans = Math.max(ans, min * (right - left));
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return ans;
}
leetCode跳转： 11. 盛水最多的容器
排序+双指针也是常见的组合解法，本题只需要排序后，再进行枚举即可。
两处优化
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
int n = nums.length;
for (int i = 0; i < n - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
if (nums[i] + nums[n - 1] + nums[n - 2] < 0) {
continue;
}
if (nums[i] + nums[i + 1] + nums[i + 2] > 0) {
break;
}
int k = n - 1;
for (int j = i + 1; j < k; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
while (j < k && nums[i] + nums[j] + nums[k] > 0) {
k--;
}
if (j == k) {
break;
}
if (nums[i] + nums[j] + nums[k] == 0) {
List<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[k]);
ans.add(list);
}
}
}
return ans;
}
leetCode跳转： 15. 三数之和
解法同三数之和
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int ans = Integer.MAX_VALUE;
int n = nums.length;
for (int i = 0; i < n - 2; i++) {
int j = i + 1;
int k = n - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
if (sum == target) {
return sum;
}
// 接近三数之和
if (Math.abs(sum - target) < Math.abs(ans - target)) {
ans = sum;
}
if (sum > target) {
k--;
} else {
j++;
}
}
}
return ans;
}
leetCode跳转： 16. 最接近的三数之和
左右指针，相向遍历。
要求可接的雨水处的水量，可以先分别求出位于此处两侧最长柱子的高度，然后取其较短的一根即表示其可接水量的上限，因此完全可以通过不断的左右遍历（收缩较短的柱子）的方式计算出每个位置可接的水量。
public int trap(int[] height) {
int n = height.length;
int leftMax = 0;
int rightMax = 0;
int left = 0;
int right = n - 1;
int ans = 0;
while (left < right) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
if (height[left] < height[right]) {
ans += leftMax - height[left];
left++;
} else {
ans += rightMax - height[right];
right--;
}
}
return ans;
}
leetCode跳转： 42. 接雨水