（LeetCode）Java 求解三数之和

喜欢ヅ旅行 2023-01-09 15:49 1阅读 0赞

### 文章目录 ###

*   *  一、题目
     *  二、代码
     *  三、总结

## 一、题目 ##

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

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

--------------------

分析：

1.  首先可以对数组进行排序；
2.  然后依次对数组中的值进行固定，然后使用左右指针指向该固定值`nums[i]`后面的两端，记为 `nums[l]`,`nums[r]`，计算三者的和是否为0，满足则记录结果；
3.  如果当前 `nums[i]` 的值大于0，则其后的所有值均大于0，所以三数之和必然会大于0，结束循环；
4.  如果 `nums[i]==nums[i-1]`，该数字重复，会导致结果重复，跳过；
5.  当 `sum==0` 时，`nums[l]==nums[l+1]`，会导致结果重复，应跳过，`l++`；
6.  当 `sum==0` 时，`nums[r]==nums[r-1]`，会导致结果重复，应跳过，`r--`；
7.  时间复杂度： O ( n 2 ) O(n^2) O(n2)，n 是数组的长度

## 二、代码 ##

public List<List<Integer>> threeSum(int[] nums) { 
            List<List<Integer>> lists = new ArrayList<>();
            if (nums == null || nums.length < 3) { 
                return lists;
            }
            //数组排序
            Arrays.sort(nums);
            //最后两个肯定不满足条件
            for (int i = 0; i < nums.length-2; i++) { 
                //如果当前数字大于0，则三数之和一定大于0，结束循环
                if (nums[i] > 0) { 
                    break;
                }
                //去除重复的数字
                if (i > 0 && nums[i] == nums[i - 1]) { 
                    continue;
                }
                int l = i + 1;
                int r = nums.length - 1;
                while (l < r) { 
                    int sum = nums[i] + nums[l] + nums[r];
                    if (sum == 0) { 
                        //记录符合条件的列表
                        lists.add(Arrays.asList(nums[i],nums[l],nums[r]));
                        //去重
                        while (l < r && nums[l] == nums[l + 1]) { 
                            l++;
                        }
                        //去重
                        while (r > l && nums[r] == nums[r - 1]) { 
                            r--;
                        }
                        l++;
                        r--;
                    } else if (sum > 0) { 
                        r--;
                    } else if (sum < 0) { 
                        l++;
                    }
                }
            }
            return lists;
        }

## 三、总结 ##

暴力解法使用三重循环，时间复杂度肯定爆炸。

要善用指针思想

排除重复的情况要考虑齐全

//返回指定大小的列表
    Arrays.asList(nums[i],nums[l],nums[r])