【leetcode】15. 三数之和(medium)

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

这题真的好难，试了好多方法，最后参考了代码随想录的解法：

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> res = new ArrayList<>();if(nums.length<3) return res;// 排序，方便操作Arrays.sort(nums);for(int i=0;i<nums.length-2;i++){// 剪枝：已经排过序了，所以如果第一个值大于0，没有可行解if(nums[i]>0) return res;// 剪枝：如果当前元素和前一个元素一样，跳过即可，否则会有重复解if((i>0) && (nums[i-1]==nums[i])) continue;int left = i+1;int right = nums.length-1;while(left < right){// int sum = nums[i]+nums[left]+nums[right];if(nums[i]+nums[left]+nums[right] == 0){res.add(Arrays.asList(nums[i], nums[left], nums[right]));while(left<right && nums[left]==nums[left+1])  //去重left++;while(left<right && nums[right]==nums[right-1])  //去重right--;left++;right--;}else if(nums[i]+nums[left]+nums[right] < 0)left++;else if(nums[i]+nums[left]+nums[right] > 0)right--;}}return res;}
}