双指针算法专题（2）

找往期文章包括但不限于本期文章中不懂的知识点：
   个人主页：我要学编程(ಥ_ಥ)-CSDN博客
  所属专栏： 优选算法专题
  想要了解双指针算法的介绍，可以去看下面的博客：双指针算法的介绍 
目录
611.有效三角形的个数
LCR 179.查找总价格为目的值的两个商品
15.三数之和
18. 四数之和

---

 
611.有效三角形的个数

题目：
   给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
  
  示例 1:

1. <strong>输入:</strong> nums = [2,2,3,4]
2. <strong>输出:</strong> 3
3. <strong>解释:</strong>有效的组合是:
4. 2,3,4 (使用第一个 2)
5. 2,3,4 (使用第二个 2)
6. 2,2,3

复制代码

示例 2:

1. <strong>输入:</strong> nums = [4,2,3,4]
2. <strong>输出:</strong> 4

复制代码

提示:
  

• 1 <= nums.length <= 1000
  
• 0 <= nums <= 1000
  

  思绪：这个题目就是想让我们在给的数组中找出可以组成三角形的个数。确定三个数是否可以组成三角形：任意两边之和大于第三边即可。
最简朴的方法就是直接遍历数组，根据三角形的判断条件暴力枚举即可。
代码实现：
错误解法：暴力枚举 

1. class Solution {
2.     // 错误解法：暴力枚举
3.     public int triangleNumber(int[] nums) {
4.         int count = 0;
5.         // 注意这里的i,j,k的位置，i最多只能倒带倒数第三个的位置,j....
6.         for (int i = 0; i <= nums.length-3; i++) {
7.             for (int j = i+1; j <= nums.length-2; j++) {
8.                 for (int k = j+1; k <= nums.length-1; k++) {
9.                     if (nums[i]+nums[j] > nums[k] &&
10.                         nums[i]+nums[k] > nums[j] &&
11.                         nums[k]+nums[j] > nums[i]
12.                         ) {
13.                             count++;
14.                     }
15.                 }
16.             }
17.         }
18.         return count;
19.     }
20. }

复制代码

由于时间复杂度过高（O(N^3)），上面的代码肯定是跑不外的。
接下来，就是想想怎么优化？
我们知道三角形的判定还有一种简朴方法：两小边之和大于最大边即可。那怎么找两小边呢？一个一个的去比较吗？这个肯定不现实。其实Arrays这类中有一个静态方法可以用来对数字举行排序( sort() ) ，知道了两小边之和，就是找最大边举行判断即可。

这里我们就通过一定的条件来优化了第三层循环，减少了循环的次数。
优化解法：定位两小边 和 最大边举行比较 

1. class Solution {
2.     // 优化解法一：定位两小边 和 最大边进行比较
3.     public int triangleNumber(int[] nums) {
4.         Arrays.sort(nums);
5.         int count = 0;
6.         for (int i = 0; i <= nums.length-3; i++) {
7.             for (int j = i+1; j <= nums.length-2; j++) {
8.                 // k此时是三个数中最大值的下标
9.                 int k = j+1;
10.                 while (k < nums.length) {
11.                     if (nums[i]+nums[j] > nums[k]) {
12.                         count++;
13.                         k++;
14.                     } else {
15.                         // 由于数组是升序，因此后面的一定大于此时的值，因此无需判断了
16.                         break;
17.                     }
18.                 }
19.             }
20.         }
21.         return count;
22.     }
23. }

复制代码

既然可以定位 两小边，那么可不可以定位 最大边呢，然后找两小边举行比较呢？答案是可以的。

优化解法：固定最大边，比较别的两边

1. class Solution {
2.     // 优化解法二：固定最大边，比较另外两边
3.     public int triangleNumber(int[] nums) {
4.         Arrays.sort(nums);
5.         int count = 0;
6.         for (int k = nums.length-1; k >=2; k--) {
7.             // 开始寻找两小边的范围值
8.             int i = 0;
9.             int j = k-1;
10.             while (i < j) {
11.                 if (nums[i]+nums[j] > nums[k]) {
12.                     count += (j-i); // 满足三角形的个数
13.                     j--; // i变化没意义
14.                 } else {
15.                     i++; // j变化没有意义
16.                 }
17.             }
18.         }
19.         return count;
20.     }
21. }

复制代码

注意：在固定最大边的优化方法中，我们只需要范围比较 nums + nums[j] 与 nums[k] 的大小关系即可。没有去一个一个的遍历比较 比较 nums + nums[j] 与 nums[k] 的大小关系。这就致使时间复杂度从 O(N^3) 降至 O(N^2)。
LCR 179.查找总价格为目的值的两个商品

题目：
   购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种环境，返回任一结果即可。
  示例 1：

1. <strong>输入：</strong>price = [3, 9, 12, 15], target = 18
2. <strong>输出：</strong>[3,15] 或者 [15,3]

复制代码

示例 2：

1. <strong>输入：</strong>price = [8, 21, 27, 34, 52, 66], target = 61
2. <strong>输出：</strong>[27,34] 或者 [34,27]

复制代码

提示：
  

• 1 <= price.length <= 10^5
  
• 1 <= price <= 10^6
  
• 1 <= target <= 2*10^6
  

  思绪： 很简朴的思绪，直接双层for循环遍历数组，去找和target的值即可。
代码实现：
错误解法：暴力枚举

1. class Solution {
2.     // 错误解法：暴力枚举
3.     public int[] twoSum(int[] price, int target) {
4.         int[] ret = new int[2];
5.         for (int i = 0; i < price.length; i++) {
6.             // 如果从j=0开始的话，就会有重复的，且可能会出现i==j的情况
7.             for (int j = i+1; j < price.length; j++) {
8.                 if (price[i]+price[j] == target) {
9.                     ret[0] = price[i];
10.                     ret[1] = price[j];
11.                     return ret;
12.                 }
13.             }
14.         }
15.         return ret;
16.     }
17. }

复制代码

上面的代码时间复杂度过高（O(N^2)），因此我们优化的方向就是降低时间复杂度为 O(N)。由于题目告诉我们了这个数组是有序的，而且知道了要查找的数据，因此我们可以对数据举行范围筛选。

通过上面的方法，我们会发现查找的服从直线上升了。其思绪的时间复杂度为 O(N)。
正确解法：使用对撞指针，减少查询的次数，降低时间复杂度 

1. class Solution {
2.     public int[] twoSum(int[] price, int target) {
3.         int[] ret = new int[2];
4.         // 通过target的值来缩小范围遍历
5.         int left = 0;
6.         int right = price.length-1;
7.         while (left < right) {
8.             if (price[left]+price[right] > target) {
9.                 // 大于目标值，得减小
10.                 right--;
11.             } else if (price[left]+price[right] < target) {
12.                 // 小于目标值。得增大
13.                 left++;
14.             } else {
15.                 ret[0] = price[left];
16.                 ret[1] = price[right];
17.                 break;
18.             }
19.         }
20.         return ret;
21.     }
22. }

复制代码

通过上面两个题目，我们可以发现一个如许的规律：对撞指针能降低一个幂次级的时间复杂度。
例如：O(N^3) 使用对撞指针后，可以降低为 O(N^2)；O(N^2) 使用对撞指针后，可以降低为 O(N)。当然，最多也只能降低至 O(N)了，不可能直接降为O(1)。
15.三数之和

题目：
   给你一个整数数组 nums ，判断是否存在三元组 [nums, nums[j], nums[k]] 满意 i != j、i != k 且 j != k ，同时还满意 nums + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
  注意：答案中不可以包含重复的三元组。
  
  示例 1：

1. <strong>输入：</strong>nums = [-1,0,1,2,-1,-4]
2. <strong>输出：</strong>[[-1,-1,2],[-1,0,1]]
3. <strong>解释：</strong>
4. nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
5. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
6. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
7. 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
8. 注意，输出的顺序和三元组的顺序并不重要。

复制代码

示例 2：

1. <strong>输入：</strong>nums = [0,1,1]
2. <strong>输出：</strong>[]
3. <strong>解释：</strong>唯一可能的三元组和不为 0 。

复制代码

示例 3：

1. <strong>输入：</strong>nums = [0,0,0]
2. <strong>输出：</strong>[[0,0,0]]
3. <strong>解释：</strong>唯一可能的三元组和为 0 。

复制代码

提示：
  

• 3 <= nums.length <= 3000
  
• -105 <= nums <= 105
  

  思绪：根据题目给出的信息来看：我们要做的事变有两步：第一，找到符合三数之和为0的数；第二，对找到的数据举行去重利用。第一步的话，起首想到的就是暴力枚举找到符合要求的数据。但是找到数据之后的去重利用是比较难的，由于三个数的固然总体是一样的，但是其内部的次序却不同，我们无法直接判断，因此这里我们就需要对数据举行排序利用。但题目又来了：与其选择找出数据之后排序，不如直接在原数组上面举行排序利用。可能有小伙伴会疑惑：为什么要在原数组上举行排序呢？如下图所示：

排完序之后，我们会发现重复的数据长得一模一样，因此这里我们可以使用一个自然的去重容器set来处置惩罚，最终得到的结果就是我们想要的答案。
代码实现：
错误解法：暴力枚举

1. class Solution {
2.     // 错误解法：暴力枚举
3.     public List<List<Integer>> threeSum(int[] nums) {
4.         List<List<Integer>> list = new ArrayList<>();
5.         // 1、先对数组整体排序
6.         Arrays.sort(nums);
7.         // 2、再去找符合条件的数据
8.         for (int i = 0; i <= nums.length-3; i++) {
9.             List<Integer> sub_list = new ArrayList<>();
10.             for (int j = i+1; j <= nums.length-2; j++) {
11.                 for (int k = j+1; k <= nums.length-1; k++) {
12.                     // 这里可以优化一点点效率：>0的话，就直接跳出循环，
13.                     // 大于0，再继续往后走也没用(根本不可能出现==0的情况)
14.                     if (nums[i]+nums[j]+nums[k] == 0) {
15.                         sub_list.add(nums[i]);
16.                         sub_list.add(nums[j]);
17.                         sub_list.add(nums[k]);
18.                         List<Integer> integerList = new ArrayList<>(sub_list);
19.                         list.add(integerList);
20.                         // 每次插入数据之后，要及时清空，保证只有三个数据
21.                         sub_list.clear();
22.                     }
23.                 }
24.             }
25.         }
26.         // 3、利用set对其去重
27.         Set<List<Integer>> set = new HashSet<>();
28.         // 遍历list将其中的元素插入set中
29.         for (int i = 0; i < list.size(); i++) {
30.             if (!set.contains(list.get(i))) {
31.                 set.add(list.get(i));
32.             }
33.         }
34.         List<List<Integer>> new_list = new ArrayList<>();
35.         // 遍历set中的元素插入到new_list
36.         for (List<Integer> x : set) {
37.             new_list.add(x);
38.         }
39.         return new_list;
40.     }
41. }

复制代码

注意：上面代码的时间复杂度过大（三层for循环+两个遍历for循环）， 会超出时间限定。在最后一个将set中的元素插入new_list 中，可能有的小伙伴会写出下面的代码。

1. for (int i = 0; i < list.size(); i++) {
2.     if (set.contains(list.get(i))) {
3.         new_list.add(list.get(i));
4.     }
5. }

复制代码

这个代码是有题目的，没有达到去重的目的。由于 list 可能中存在着多份雷同的数据，但是在set 中只存在一份。因此当我们用 list 中的元素去遍历set 时，就会出现重复的元素，最终还是没有达到去重的结果。如下所示：

优化的思绪有两个：1、对于查找数据时，使用对撞指针来举行优化。即通过最外层循环来固定一个数，然后再用对撞指针来找符合要求的数据。2、对去重的优化。set 去重固然简朴方便，但是两个for循环也带来了不少时间上的斲丧。
1、优化查找数据：

正确解法：对撞指针优化查找数据 

1. class Solution {
2.     // 正确解法：使用对撞指针降低时间复杂度
3.     public List<List<Integer>> threeSum(int[] nums) {
4.         List<List<Integer>> list = new ArrayList<>();
5.         // 1、先对数组整体排序
6.         Arrays.sort(nums);
7.         // 2、再去找符合条件的数据
8.         for (int i = 0; i <= nums.length-3; i++) {
9.             List<Integer> sub_list = new ArrayList<>();
10.             int j = i+1;
11.             int k = nums.length-1;
12.             while (j < k) {
13.                 if (nums[i]+nums[j]+nums[k] == 0) {
14.                         sub_list.add(nums[i]);
15.                         sub_list.add(nums[j]);
16.                         sub_list.add(nums[k]);
17.                         List<Integer> integerList = new ArrayList<>(sub_list);
18.                         list.add(integerList);
19.                         sub_list.clear();
20.                         // 只有一个增大，另一个减小，才可能达到相等
21.                         // 这里如果不是两个同时走的话，就会超出时间限制
22.                         j++;
23.                         k--;
24.                 } else if (nums[i]+nums[j]+nums[k] > 0) {
25.                     // 得减小，k--
26.                     k--;
27.                 } else { // < 0
28.                     // 得增加，j++
29.                     j++;
30.                 }
31.             }
32.         }
33.         // 3、利用set对其去重
34.         Set<List<Integer>> set = new HashSet<>();
35.         // 遍历list将其中的元素插入set中
36.         for (int i = 0; i < list.size(); i++) {
37.             if (!set.contains(list.get(i))) {
38.                 set.add(list.get(i));
39.             }
40.         }
41.         List<List<Integer>> new_list = new ArrayList<>();
42.         // 遍历set中的元素插入到new_list中
43.         for (List<Integer> x : set) {
44.             new_list.add(x);
45.         }
46.         return new_list;
47.     }
48. }

复制代码

上面的代码固然可以通过全部的测试用例，但是时间服从非常之低。因此就要开始尝试看看能不能对去重利用举行优化。而最抱负的优化就是能在找数据的同时去重。即在查找数据时，不把重复的数据算入其中，这就直接从源头上杜绝了去重的利用。那怎样才气找到不重复的数据呢？
我们会发现一个规律：当数据重复时，结果一定是雷同的。即找到一组符合要求的数据之后，假如 j 对应的值 和 上一次 j 对应的值是一样的，那么就可以跳过，由于上一次 j 对应的值已经和其他值举行了结合检查。假如可以，那么就成了一次重复的数据；反之，上一次也检查过了。同理，k、i也是如此。当要注意一个数组越界题目。

1. class Solution {
2.     // 正确解法：对撞指针+查找去重
3.     public List<List<Integer>> threeSum(int[] nums) {
4.         List<List<Integer>> list = new ArrayList<>();
5.         // 1、先对数组整体排序
6.         Arrays.sort(nums);
7.         // 2、再去找符合条件的数据
8.         for (int i = 0; i <= nums.length-3; i++) {
9.             // 与上一次的值相同，就不需要再进行重复的操作了
10.             while (i-1 >= 0 && i <= nums.length-3 && nums[i] == nums[i-1]) {
11.                 i++;
12.             }
13.             // i对应的值一定是数组中最小的值，如果它都>0了，那肯定找不到了
14.             while (i < nums.length && nums[i] > 0) {
15.                 i++;
16.             }
17.             List<Integer> sub_list = new ArrayList<>();
18.             int j = i+1;
19.             int k = nums.length-1;
20.             while (j < k) {
21.                 if (nums[i]+nums[j]+nums[k] == 0) {
22.                         sub_list.add(nums[i]);
23.                         sub_list.add(nums[j]);
24.                         sub_list.add(nums[k]);
25.                         List<Integer> integerList = new ArrayList<>(sub_list);
26.                         list.add(integerList);
27.                         sub_list.clear();
28.                         // 只有一个增大，另一个减小，才可能达到相等
29.                         // 这里如果不是两个同时走的话，就会超出时间限制
30.                         j++;
31.                         k--;
32.                         // 如果和上一次的数据相同，则跳过
33.                         while (j < k && nums[j] == nums[j-1]) {
34.                             j++;
35.                         }
36.                         while (j < k && nums[k] == nums[k+1]) {
37.                             k--;
38.                         }
39.                 } else if (nums[i]+nums[j]+nums[k] > 0) {
40.                     // 得减小，k--
41.                     k--;
42.                     // 数据与上一次相同的话，查找出来的还是同样的结果
43.                     while (j < k && nums[k] == nums[k+1]) {
44.                         k--;
45.                     }
46.                 } else { // < 0
47.                     // 得增加，j++
48.                     j++;
49.                     // 数据与上一次相同的话，查找出来的还是同样的结果
50.                     while (j < k && nums[j] == nums[j-1]) {
51.                         j++;
52.                     }
53.                 }
54.             }
55.         }
56.         return list;
57.     }
58. }

复制代码

总的来说，这一题还是比较难的。既要想要去重的方法（使用set大概查找时排序雷同的元素），还要避免时间复杂度过高的环境下查找数据（使用对撞指针举行优化处置惩罚）。 
 接下来，我们再来做一道与这个极其相似的题目。
18. 四数之和

题目：
   给你一个由 n 个整数组成的数组 nums ，和一个目的值 target 。请你找出并返回满意下述全部条件且不重复的四元组 [nums[a], nums, nums[c], nums[d]] （若两个四元组元素逐一对应，则以为两个四元组重复）：
  

• 0 <= a, b, c, d < n
  
• a、b、c 和 d 互不雷同
  
• nums[a] + nums + nums[c] + nums[d] == target
  

  你可以按 任意次序 返答复案 。
  
  示例 1：

1. <strong>输入：</strong>nums = [1,0,-1,0,-2,2], target = 0
2. <strong>输出：</strong>[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

复制代码

示例 2：

1. <strong>输入：</strong>nums = [2,2,2,2,2], target = 8
2. <strong>输出：</strong>[[2,2,2,2]]

复制代码

提示：
  

• 1 <= nums.length <= 200
  
• -109 <= nums <= 109
  
• -109 <= target <= 109
  

  思绪：和三数之和简直就是孪生兄弟。 同样是先排序，再去查找数据（这里只展示优化后的思绪和解法，想看推导过程和暴力枚举到优化的过程，可见三数之和）。
代码实现：
错误解法：用双层对撞指针取代四层for循环+内部去重

1. class Solution {
2.     // 双层对撞指针会忽略一些数据
3.     public List<List<Integer>> fourSum(int[] nums, int target) {
4.         List<List<Integer>> list = new ArrayList<>();
5.         Arrays.sort(nums);
6.         int i = 0;
7.         int j = nums.length-1;
8.         while (i < j) {
9.             List<Integer> sub_list = new ArrayList<>();
10.             // 注意left和right的取值
11.             int left = i+1;
12.             int right = j-1;
13.             while (left < right) {
14.                 // 注意：对于内层循环来说，只有left和right是可变化的，i、j都是固定的
15.                 if (nums[i]+nums[j]+nums[left]+nums[right] == target) {
16.                     sub_list.add(nums[i]);
17.                     sub_list.add(nums[j]);
18.                     sub_list.add(nums[left]);
19.                     sub_list.add(nums[right]);
20.                     List<Integer> integerList = new ArrayList<>(sub_list);
21.                     list.add(integerList);
22.                     sub_list.clear();
23.                     left++;
24.                     right--;
25.                     while(left < right && nums[right] == nums[right+1]) {
26.                         right--;
27.                     }
28.                     while(left < right && nums[left] == nums[left-1]) {
29.                         left++;
30.                     }
31.                 } else if (nums[i]+nums[j]+nums[left]+nums[right] > target) {
32.                     right--;
33.                     while(left < right && nums[right] == nums[right+1]) {
34.                         right--;
35.                     }
36.                 } else {
37.                     left++;
38.                     while(left < right && nums[left] == nums[left-1]) {
39.                         left++;
40.                     }
41.                 }
42.             }
43.             i++;
44.             j--;
45.             while (i < j && nums[i] == nums[i-1]) {
46.                 i++;
47.             }
48.             while (i < j && nums[j] == nums[j+1]) {
49.                 j--;
50.             }
51.         }
52.         return list;
53.     }
54. }

复制代码

上面代码的思绪确实不错，的确可以减少不少时间的斲丧，但是会遗漏一些数据。
当 nums = [-3, -1, 0, 2, 4, 5]、target = 0时，是找不到数据的。 感兴趣的小伙伴可以本身去测一测。（原来，我开始也是想到用这种方法来写，感觉服从应该会很高，但是后面经过调试发现，根本就找不出来上面的数据。）
正确解法：使用双层for循环+一层对撞指针+查找数据时去重 

1. class Solution {
2.     public List<List<Integer>> fourSum(int[] nums, int target) {
3.         List<List<Integer>> list = new ArrayList<>();
4.         // 1、排序
5.         Arrays.sort(nums);
6.         // 2、开始找数据+去重操作
7.         for (int i = 0; i <= nums.length-4;) {
8.             for (int j = i+1; j <= nums.length-3;) {
9.                 List<Integer> sub_list = new ArrayList<>();
10.                 int left = j+1;
11.                 int right = nums.length-1;
12.                 while (left < right) {
13.                     if (((long)nums[i]+nums[j]+
14.                             nums[left]+nums[right]) == target) {
15.                         sub_list.add(nums[i]);
16.                         sub_list.add(nums[j]);
17.                         sub_list.add(nums[left]);
18.                         sub_list.add(nums[right]);
19.                         List<Integer> integerList = new ArrayList<>(sub_list);
20.                         list.add(integerList);
21.                         sub_list.clear();
22.                         left++;
23.                         right--;
24.                         while(left < right && nums[right] == nums[right+1]) {
25.                             right--;
26.                         }
27.                         while(left < right && nums[left] == nums[left-1]) {
28.                             left++;
29.                         }
30.                     } else if ((long)nums[i]+nums[j]+
31.                             nums[left]+nums[right] > target) {
32.                         right--;
33.                         while(left < right && nums[right] == nums[right+1]) {
34.                             right--;
35.                         }
36.                     } else {
37.                         left++;
38.                         while(left < right && nums[left] == nums[left-1]) {
39.                             left++;
40.                         }
41.                     }
42.                 }
43.                 j++;
44.                 while (j <= nums.length-3 && nums[j] == nums[j-1]) {
45.                     j++;
46.                 }
47.             }
48.             i++;
49.             while (i >= 1 && i <= nums.length-4 && nums[i] == nums[i-1]) {
50.                 i++;
51.             }
52.         }
53.         return list;
54.     }
55. }

复制代码

注意：
1、

因此我们在盘算四数之和时强转为了 long类型。
2、

总体来说：三数之和和四数之和还是有点难度的，不但需要编码能力强，思绪也要清新。
好啦！本期 双指针算法专题（2）的学习之旅就到此竣事啦！我们下一期再一起学习吧！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。