ToB企服应用市场:ToB评测及商务社交产业平台

标题: 三数之和(双指针法) [打印本页]

---

作者: 尚未崩坏    时间: 2024-8-4 09:51
标题: 三数之和(双指针法)
题目描述

给你一个整数数组 nums ，判定是否存在三元组 [nums, nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums + nums[j] + nums[k] == 0 。请你返回全部和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

双指针法：首先我们要对数组进行排序,我们开始遍历数组从0下标开始记为i，界说left指针为i+1,right指针为nums.length-1(最后一位),然后开始收集结果，如果我们的nums+nums[left]+nums[right]0则right指针左移一位，如果等于0则加入结果会合，但是这里有很多去重的细节，我们看以下代码中的解法。

1. import java.util.*;
2. class Solution {
3.     public List<List<Integer>> threeSum(int[] nums) {
4.         int left;
5.         int right;
6.         Arrays.sort(nums);
7.         List<List<Integer>> result=new ArrayList<>();
8.         
9.         for(int i=0;i<nums.length-2;i++){
10.             if(nums[i]>0){
11.                 return result;
12.             }
13.                         //如果和前一位相同的话我们再遍历数组就会有重复的结果集，我们直接跳过进入下一次循环
14.             if(i>0 && nums[i]==nums[i-1] ){
15.                 continue;
16.             }
17.             left=i+1;
18.             right=nums.length-1;
19.             while(left<right){
20.                 if(nums[i]+nums[left]+nums[right]<0){
21.                     left++;
22.                 }else if(nums[i]+nums[left]+nums[right]>0){
23.                     right--;
24.                 }else{
25.                     List<Integer> list=new ArrayList<>();
26.                     list.add(nums[i]);
27.                     list.add(nums[left]);
28.                     list.add(nums[right]);
29.                     result.add(list);
30.                     //这一步操作看下图错误实例,这一步也是结果集去重的关键
31.                     while (right > left && nums[right] == nums[right - 1]) {
32.                         right--;
33.                     }
34.                     while (right > left && nums[left] == nums[left + 1]) {
35.                         left++;
36.                     }
37.                     left++;
38.                     right--;
39.                 }
40.             }
41.         }
42.         return result;
43.     }
44. }

复制代码

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

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4