Leetcode刷题100天—15. 三数之和( 排序)—day30

我会带着你远行 2022-09-12 09:49 151阅读 0赞

前言：

> 作者：神的孩子在歌唱
> 
> 大家好，我叫运智

![image-20210906211914241][]

#### [15. 三数之和][15.] ####

难度中等3716收藏分享切换为英文接收动态反馈

给你一个包含 `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`

package 排序;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    public class _15_三数之和 { 
        public List<List<Integer>> threeSum(int[] nums) { 
    // 设定一个二维列表
        	List<List<Integer>> res=new ArrayList<List<Integer>>();
    // 排序
        	Arrays.sort(nums);
    // 初始化指针
        	int left=0;
    
    // while循环直到左指针大于0结束
        	while(left<nums.length&&nums[left]<=0) { 
    // 定义一个可以在左右指针中间遍历的指针
        		int pivot=left+1;
    // 定义右指针
                int right=nums.length-1;
    
    // 如果前一个数和后一个数相等那么跳过循环去除重复值
        		if (left>0&&nums[left]==nums[left-1]) { 
        			left++;
    				continue;
    			}
    // 如果pivot等于right就结束循环
        		while(pivot<right) { 
    // 如果有重复的数就退出
            		if (pivot>left+1&&nums[pivot]==nums[pivot-1]) { 
    					pivot++;
                        continue;
    				}
    // 如果符合条件
            		else if (nums[left]+nums[pivot]+nums[right]==0) { 
    // 将这三个数存入列表,在存入二维列表
            			res.add(new ArrayList<Integer>(Arrays.asList(nums[left],nums[pivot],nums[right])));
                        pivot++;
                        right--;
        			}
    // 否则如果大于num>0,说明右边的数太大right--
            		else if (nums[left]+nums[pivot]+nums[right]>0) { 
        				right--;
        			}
    // 否则如果小于0,说明左边数太小pivot++
            		else { 
        				pivot++;
        			}
        		}
    // left加一继续判断
        		left++;
    
        	}
        	return res;
        }
        public static void main(String args[]) { 
        	int[] nums= { -1,0,1,2,-1,-4};
        }
    }
    /* * 思路：[-1,0,1,2,-1,-4] * 排序sort:[-4,-1,-1,0,1,2] * 设定两个指针left 和 right在定义他们中间移动的数pivot * 如果left+pivot+right==0那么pivot=++,right-- * 如果pivot==right结束循环,进行下一循环left++ pivot=left+1 */

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114
> 
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210906211914241]: /images/20220828/004c4a04de6f4f64a3d5c4b331f4f08f.png
[15.]: https://leetcode-cn.com/problems/3sum/