LeetCode-双指针总结

62 阅读 0 评论 41 点赞

我是靠谱客的博主危机大白，最近开发中收集的这篇文章主要介绍LeetCode-双指针总结，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

--双指针--

双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。

通过双指针可大大优化复杂度，减小因多重循环浪费的时间。

例题一：two-sum-ii-input-array-is-sort

题目描述：在有序数组中找出两个数，使它们的和为 target。

使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。

如果两个指针指向元素的和 sum == target，那么得到要求的结果；
如果 sum > target，移动较大的元素，使 sum 变小一些；
如果 sum < target，移动较小的元素，使 sum 变大一些。

class Solution {
public int[] twoSum(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return new int[2];
}
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int other = target - nums[i];
if (map.containsKey(other)) {
return new int[]{map.get(other), i};
} else {
map.put(nums[i], i);
}
}
return new int[2];
}
}

例题二：3sum

题目描述：给出一个数组，找出数组中任意三个数字的和为0的所有组合情况，返回一个列表。

可利用上一题的思路，现将该数组排序，先指定一个值，另外两个值通过双指针移动，找到解。

class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (nums[i] > 0) { //最小值大于0，说明该数组没有负数，不可能有解
break;
}
if (i != 0 && nums[i] == nums[i-1]) {
continue;
}
int tmp = -nums[i];
int lo = i + 1;
int hi = nums.length - 1;
while(lo < hi) {
if (nums[lo] + nums[hi] < tmp) {
lo++;
while(hi > lo && nums[lo] == nums[lo - 1]) lo++;
} else if (nums[lo] + nums[hi] > tmp) {
hi--;
while(hi > lo && nums[hi] == nums[hi + 1]) hi--;
} else {
res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
lo++; hi--;
while(hi > lo && nums[lo] == nums[lo - 1]) lo++;
while(hi > lo && nums[hi] == nums[hi + 1]) hi--;
}
}
}
return res;
}
}

例题三：4sum

题目描述：给出一个数组，找出任意四个数等于target的所有组合解，返回一个列表。

这时候，外部就要通过两重循环指定两个值，然后通过双指针移动，找出解。

class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> list = new ArrayList<List<Integer>>();
if (nums == null || nums.length < 4)
return list;
Arrays.sort(nums);
for (int i = 0; i < nums.length - 3; i++) {
if(i > 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1;j < nums.length - 2;j++) {
if(j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
int low = j + 1, high = nums.length - 1;
while (low < high) {
if(nums[i] + nums[j] + nums[low] + nums[high] == target) {
list.add(Arrays.asList(nums[i], nums[j], nums[low], nums[high]));
while(low < high && nums[low] == nums[low + 1]) low++;
while(low < high && nums[high] == nums[high - 1]) high--;
low++;
high--;
} else if (nums[i] + nums[j] + nums[low] + nums[high] < target) {
low++;
} else if(nums[i] + nums[j] + nums[low] + nums[high] > target) {
high--;
}
}
}
}
return list;
}
}

例题四：sum-of-square-numbers

题目描述：给出一个数字，找出是否存在两个数的平方和等于该数字，如果有返回true，否则返回false。

class Solution {
public boolean judgeSquareSum(int c) {
if (c < 0) {
return false;
}
int i = 0, j = (int)Math.sqrt(c);
while (i <= j) {
int sum = i * i + j * j;
if (sum == c) {
return true;
} else if (sum > c) {
j--;
} else if (sum < c) {
i++;
}
}
return false;
}
}

双指针的题型暂时总结到这里，这种思想可以帮我们降低程序的复杂度，减少程序中的循环语句带来的不必要的时间损耗。