[关闭]
@yexiaoqi 2022-05-30T09:49:27.000000Z 字数 884 阅读 287

15. 三数之和

刷题 leetcode


题目:给你一个包含 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

链接https://leetcode.cn/problems/3sum


  1. class Solution {
  2. public List<List<Integer>> threeSum(int[] nums) {
  3. List<List<Integer>> list = new ArrayList<>();
  4. if(nums==null || nums.length<3) return list;
  5. Arrays.sort(nums);
  6. for(int i=0; i<nums.length; i++){
  7. if(nums[i]>0) break;//最小的数大于0,说明没有符合条件的
  8. if(i>0 && nums[i]==num[i-1]) continue;//有相邻重复的去重
  9. int left=i+1;//左指针
  10. int right=nums.length-1;//右指针
  11. while(left<right){
  12. int sum=nums[i]+nums[left]+nums[right];
  13. if(sum==0){
  14. list.add(Arrays.asList(nums[i],nums[left],nums[right]);
  15. while(left<right && nums[left]==nums[left+1]) left++;//去重
  16. while(left<right && nums[right]==nums[right-1]) right--;//去重
  17. left++;
  18. right--;
  19. } else if(sum>0) right--;
  20. else left++;
  21. }
  22. }
  23. return list;
  24. }
  25. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注