三数之和Java实现（力扣15/1557）

我就是我 2023-05-28 15:54 8阅读 0赞

力扣刷题小记

**题目描述如下：**

**给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。**

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

**示例：**

**给定数组 nums = \[-1, 0, 1, 2, -1, -4\]，**

**满足要求的三元组集合为：  
\[  
  \[-1, 0, 1\],  
  \[-1, -1, 2\]  
\]**

**来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/3sum  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。**

**————————————————————————————————————————————————————————————————————————————————————————————————————————————————**

**思路描述：**

**核心计算 nums\[i\]+nums\[j\]+nums\[k\]=0 ?**

暴力方法很容易想到，三重循环时间复杂度O(n^3),很明显提交后会超时。

不管用何种方法，我们必定先确定一个基准值，这里我们先确定nums\[i\] ,即把 i 作为外层循环的索引,只需要把 i 从0 遍历到 len-3。下面介绍一种头尾指针法，可以达到O(n^2)复杂度。这里必须先对原始数列进行排序，这也是能使用头尾指针进行移动的前提，如果不用头尾指针，那么必定根据双重循环对nums\[j\] 和 nums\[k\] 的值进行遍历，必定达到时间复杂度O(n^3)

下面画图帮助理解：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvbmdodTE0NTg3MDA3_size_16_color_FFFFFF_t_70][]

还有一个重点是去重问题，去除重复的结果序列，在下面的注释中给出了方法：要考虑去除重复的 j 和重复的 k

举例就是：原始数据 \[ 0, 1, -2 ,1 ,-1 \]

排序后  \[ -2, -1, 0, 1, 1\]

取完 \[ -1,0,1\] 要避免再次取 \[ -1, 0, 1\]

**代码及注释如下：**

class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
             Arrays.sort(nums);//数组从小到大排序，快排
            int len=nums.length;
            List <List<Integer>> resL=new ArrayList<>();
            if(len<3||nums[0]>0||nums[len-1]<0)return resL;//长度不足或者最大值为负最小值为正返回空列表
            int i=0,j,k;
            for(;i<len-2;i++){//第一个基准值
                if(nums[i]>0)break;//基准值大于零，因为从小到大排序的，所以直接结束循环
                if(i>0&&nums[i-1]==nums[i])continue;//基准值重复，后面相同的的基准值不用判断
                j=i+1;//头指针
                k=len-1;//尾指针
                while(j<k){
                    if(nums[i]+nums[j]+nums[k]==0){
                        List<Integer> tmpL=new ArrayList<>();//临时存储的列表
                        tmpL.add(nums[i]);
                        tmpL.add(nums[j]);
                        tmpL.add(nums[k]);                    
                        while(k-1>j&&nums[k]==nums[k-1])k--;//尾指针的值重复，后面相同的的尾指针值不用判断
                        resL.add(tmpL);
                        j++;//添加过后，头指针往里移
                        k--;//添加过后，尾指针往里移
                    }else if(nums[i]+nums[j]+nums[k]<0){//和小于0，头指针往里移动
                        j++;
                    }else{//和大于0，尾指针往里移动
                        k--;
                    }
                }
            }
            return resL;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvbmdodTE0NTg3MDA3_size_16_color_FFFFFF_t_70]: /images/20230528/238ca7ac72dc42b695c73196e2ff4e2d.png