【LeetCode-中等题】15. 三数之和

题目

在这里插入图片描述

题解一：双指针法

图解参考链接：画解算法：15. 三数之和
在这里插入图片描述
详解参考代码随想录讲的非常好
梦破碎的地方！| LeetCode：15.三数之和

代码：

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> ans = new ArrayList<>();//定义最后存放三元组的list集合if(nums.length<3||nums == null)  return ans;//若数组元素个数小于3或为空，直接返回空集合Arrays.sort(nums);//对数组进行排序//循环数组，拿出每一个元素当做a              a+b+c = 0；for(int i=0;i<nums.length;i++){if(nums[i]>0) break; // 因为是排序好的数组，如果当前数字大于0，则三数之和一定大于0，所以结束循环 if(i>0&&nums[i]==nums[i-1]) continue;  //给每个相同的nums元素去重，不然会有重复的三元组的int left = i+1;//左指针  相当于bint right = nums.length -1;//右指针  相当于cwhile(left<right){//为什么条件不是left<=right  ，因为如果设置等于了，//那么如果在相等的情况下构成了三元组，其实right和left是同一个数，肯定不行。int sum = nums[i] + nums[right] + nums[left];//计算abc的值是否为0 if(sum>0)  right--;  //如果sum大于0代表，需要缩小sun的值，那么只能通过把大值调小，才能更加靠近0else if(sum<0) left++;//同理else if(sum == 0){//满足条件List<Integer> list = Arrays.asList(nums[i],nums[left],nums[right]);//将满足条件的三个元素加入到list集合中ans.add(list);//把满足条件的三元组加入到最后的三元组大集合中//对right  和  left的去重   -1    -1      -1      0       1      2      2         三元组 -1 -1   2//                        nums  left                                  right//                          -1    -1      -1      0       1      2      2//                         nums          left                  right             三元组 -1  -1   2while(left < right&&nums[left] == nums[left + 1])  left++;while(left < right&&nums[right] == nums[right - 1]) right--;left++;right--;}}}return ans;}
}