【腾讯精选练习 50 题】16—三数之和【中等】

r囧r小猫 2022-11-19 01:17 174阅读 0赞

## 题目链接 ##

[15. 三数之和【中等】][15.]

## 题目简介 ##

给你一个包含 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]
    输出：[]

## 题目解析 ##

1.  题目要求使用不重复的三个数字， 形成 `a + b + c = 0`
2.  我们选取 `a` 时，正常的选取即可，对于 `b` 和 `c` 的选取，需要使用 `双指针法`，将复杂度进行优化
3.  对于是否重复，我们主要在以下两个方面
    
     *  选取 `a` 时，我们需要判断 `nums[i]` 与 `nums[i - 1]` 的关系，如果相等的话，表明当前数字已被用过，跳过即可
     *  选取 `b` 和 `c`，如果已经选中了 `b` 和 `c`，那么需要判断 `下一个是否还是 b` 和 `下一个是否还是 c`，是的话，需要进行跳过处理
4.  对于特殊的样例，比如 `[0,0,0]` 这种的，我们需要考虑 `i == 0` 的情况，特殊的进行判断一下即可

## 题目代码 ##

class Solution {
        
        public List<List<Integer>> threeSum(int[] nums) {
        
            Arrays.sort(nums);
    
            List<List<Integer>> list = new ArrayList<>();
            
            if(nums.length <= 2){
        
                return list;
            }
           
            for(int i = 0; i < nums.length; i++){
        
                int target = nums[i];
                // 排除重复的
                if(i > 0 && nums[i] != nums[i - 1]){
        
    
                    int left = i + 1;
                    int right = nums.length - 1;
    
                    while(left < right){
        
                        if(target + nums[left] + nums[right] == 0){
        
                            List<Integer> list1 = new ArrayList<>();
                            list1.add(target);
                            list1.add(nums[left]);
                            list1.add(nums[right]);
                            list.add(list1);
                            // 排除有重复的
    
                            while(left < nums.length - 1 && nums[left] == nums[left + 1]){
        
                                left++;
                            }
                            left++;
                            while(right > 0 && nums[right] == nums[right - 1]){
        
                                right--;
                            }
                            right--;
                        }else if(target + nums[left] + nums[right] > 0){
        
                            // 数据太大了，需要减少
                            right--;
                        }else{
        
                            left++;
                        }
                    }
                }
            }
    
            return list;
        }
    }

[15.]: https://leetcode-cn.com/problems/3sum/