我是靠谱客的博主 危机大白,这篇文章主要介绍LeetCode-双指针总结,现在分享给大家,希望可以做个参考。

--双指针--

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

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

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

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

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

  • 如果两个指针指向元素的和 sum == target,那么得到要求的结果;
  • 如果 sum > target,移动较大的元素,使 sum 变小一些;
  • 如果 sum < target,移动较小的元素,使 sum 变大一些。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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的所有组合情况,返回一个列表。

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

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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的所有组合解,返回一个列表。

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

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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; } }

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

最后

以上就是危机大白最近收集整理的关于LeetCode-双指针总结的全部内容,更多相关LeetCode-双指针总结内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(85)

评论列表共有 0 条评论

立即
投稿
返回
顶部