题目地址(15. 三数之和)

https://leetcode-cn.com/problems/3sum/

题目描述

  1. 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
  3. 注意：答案中不可以包含重复的三元组。
  7. 示例 1：
  9. 输入：nums = [-1,0,1,2,-1,-4]
  10. 输出：[[-1,-1,2],[-1,0,1]]
  13. 示例 2：
  15. 输入：nums = []
  16. 输出：[]
  19. 示例 3：
  21. 输入：nums = [0]
  22. 输出：[]
  27. 提示：
  29. 0 <= nums.length <= 3000
  30. -105 <= nums[i] <= 105

前置知识


公司

  • 暂无

思路

15.三数之和.gif
使用双指针法解决
拿这个nums数组来举例，首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。
依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i] b = nums[left] c = nums[right]。
接下来如何移动left 和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。
如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。

关键点


代码

  • 语言支持：Java

Java Code:

  1. class Solution {
  2.         public List<List<Integer>> threeSum(int[] nums) {
  3.             //将数组先排好序
  4.             Arrays.sort(nums);
  5.             ArrayList<List<Integer>> result = new ArrayList<>();
  6.             for (int i = 0; i < nums.length; i++) {
  7.                 //如果排好序的第一个数字就大于0 可以证明不会有3个数字相加=0
  8.                 if(nums[i]>0){
  9.                     return result;
  10.                 }
  11.                 // 如果开头的数字相同的话 就让数字后移 跳出当前循环 防止重复数组的产生
  12.                 if(i>0 && nums[i] == nums[i-1]){
  13.                     continue;
  14.                 }
  15.                 //双指针 指向当前循环数组的左端+1和右边
  16.                 int left = i+1;
  17.                 int right = nums.length-1;
  18.                 //边界条件 left>right证明当前循环结束
  19.                 while (left<right) {
  20.                     //3个数字相加大于0 将最大的数字right向左移 反之将left向右移
  21.                     if (nums[i] + nums[left] + nums[right] > 0) {
  22.                         right--;
  23.                     }else if (nums[i] + nums[left] + nums[right] < 0){
  24.                         left++;
  25.                     //第三种情况就是=0
  26.                     }else {
  27.                         //将3个数字组成数组添加到result中
  28.                         result.add(Arrays.asList(nums[i], nums[left], nums[right]));
  29.                         //满足下面两个条件的话 就会出现返回相同的数组
  30.                         while (left < right && nums[left] == nums[left+1]) {
  31.                             left++;
  32.                         }
  33.                         while (left < right && nums[right] == nums[right-1]) {
  34.                             right--;
  35.                         }
  36.                         //添加完后将left和right向内侧移动
  37.                         left++;
  38.                         right--;
  39.                     }
  40.                 }
  41.             }
  42.             return result;
  43.         }
  44.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：15. 三数之和 - 图2#card=math&code=O%28n%5E2%29&id=f6LKZ)
  • 空间复杂度：15. 三数之和 - 图3#card=math&code=O%28n%29&id=Vb0KQ)