LeetCode_数组_中等_15.三数之和

目录

• 1.题目
• 2.思路
• 3.代码实现（Java）

1.题目

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

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]

输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = []

输出：[]

示例 3：

输入：nums = [0]

输出：[]

提示：

0 <= nums.length <= 3000

-105 <= nums[i] <= 105

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/3sum

2.思路

（1）暴力穷举法

其思想是使用三层for循环，穷举所有可能的情况，将符合题目条件的及结果保存到res中。由于该方法的时间复杂度较高，所以在LeetCode上提交时会显示超出时间限制的提示。值得注意的是在查找的过程中要去掉重复的三元组。

（2）排序+双指针法

先对数组进行排序，可以直接使用Java中内置的方法或者自己编写排序算法。然后遍历数组中的第1~n-2个元素nums[i]，若该元素大于0，则说明后面不存在符合题目条件的三元组，直接退出循环。否则与之前的题目两数之和类似，采用双指针法，查找在nums[i]之后是否存在和为-nums[i]的两个元素。在查找的过程中要注意去掉重复的三元组。

3.代码实现（Java）

//（1）暴力穷举法
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) break;
        //剪枝操作
        if(nums[i]+nums[i+1]+nums[i+2]>0) break;
        if(nums[i]+nums[nums.length-1]+nums[nums.length-2]<0) continue;
        //在排序后，条件nums[i] == nums[i-1]的目的是防止包含重复的三元组
        if(i>0 && nums[i]==nums[i-1]) continue;
        for(int j=i+1;j<nums.length-1;j++){
        	//剪枝操作
        	if(nums[i]+nums[j]+nums[j+1]>0) break;
       	 	if(nums[i]+nums[j]+nums[nums.length-1]<0) continue;
            //去掉重复的三元组
            if(j>i+1 && nums[j]==nums[j-1]) continue;
            for(int k=j+1;k<nums.length;k++){
            	//剪枝操作
        		if(nums[i]+nums[j]+nums[k]>0) break;
       	 		if(nums[i]+nums[j]+nums[nums.length-1]<0) continue;
                //去掉重复的三元组
                if(k>j+1 && nums[k]==nums[k-1]) continue;
                if(nums[i]+nums[j]+nums[k]==0){
                    res.add(new ArrayList<>(Arrays.asList(nums[i],nums[j],nums[k])));
                }
            }
        }
    }
    return res;
}
           

//（2）排序+双指针法
public List<List<Integer>> threeSum(int[] nums) {
    //对数组进行排序
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    for(int k = 0; k < nums.length - 2; k++){
        //如果在排序后找的第一个元素为正数，则说明后面不存在符合题目条件的三元组
        if(nums[k] > 0) break;
        //剪枝操作
        if(nums[k]+nums[k+1]+nums[k+2]>0) break;
        if(nums[k]+nums[nums.length-1]+nums[nums.length-2]<0) continue;
        //在排序后，条件nums[k] == nums[k-1]的目的是防止包含重复的三元组
        if(k>0 && nums[k] == nums[k-1]) continue;
        int i=k+1, j=nums.length-1;
        while(i < j){
            int sum = nums[k] + nums[i] + nums[j];
            if(sum<0){
                while(i < j && nums[i] == nums[++i]);
            }else if(sum>0) {
                while(i < j && nums[j] == nums[--j]);
            }else{
                //将找到的三元组保存起来
                res.add(new ArrayList<>(Arrays.asList(nums[k],nums[i],nums[j])));
                while(i < j && nums[i] == nums[++i]);
                while(i < j && nums[j] == nums[--j]);
            }
        }
    }
    return res;
}