LeetCode 刷题记录（15）—Java语言

15. 三数之和

题目

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

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

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

思路

题目意思很明了，但是通过语言实现却有点复杂，为了提升算法效率必须进行一些重复操作的省略，可以通过以下方式进行重复操作的省略的判断

• 通过给nums排序，判断当前数字与前一个数字是否相当，如果相等即可省略下一步操作。
• 因为要判断三数之和为0,至少要有一正一负两个数或者全为0，那么排序之后第一个数>0或者最后一个数<0都表示不存在这样的三个数

• 在循环判断的时候如果左边的第一个数已经>0了或者右边的数已经<0了都可以结束判断。

  代码

  class Solution {
        
  public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> res = new ArrayList<>();if(nums==null||nums.length<3)return res;Arrays.sort(nums);if(nums[nums.length-1]<0||nums[0]>0)return res;for(int i=0;i<nums.length;++i){if(nums[i]>0)break;if(i==0||i>0&&nums[i]!=nums[i-1]){int j=i+1,k=nums.length-1;while(j<k&&nums[k]>=0){int total = nums[i]+nums[j]+nums[k];if(total>0)--k;else if(total<0)++j;else{List<Integer> temp = new ArrayList<>();temp.add(nums[i]);temp.add(nums[j]);temp.add(nums[k]);res.add(temp);++j;--k;while(j<k&&nums[j]==nums[j-1])++j;while(j<k&&nums[k]==nums[k+1])--k;}}}}return res;}
  }