LeetCode 15三数之和解答

LeetCode 15

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

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

解答思路如下;

(1)暴力排序然后三套循环再用set去重会导致超时，

（2）推荐使用map存下键值映射表进行计算，将题目求解降维，由因子逆时针寻找结果。

（3）去重的核心操作就是循环时判断num[i-1]!=num[i] ,这个限制条件。

解法虽然不是最优但是是在题目要求的时间，不超时 代码如下：

class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> list=new ArrayList<>(); if(nums.length<3) { return list; } Arrays.sort(nums); Map<Integer,Integer> map=new HashMap<>(nums.length); for(int i=0;i<nums.length;i++) { map.put(nums[i],i); } int sum=0; for(int i=0;i<nums.length-1;i++) { // 去重操作核心 if(i==0||nums[i-1]!=nums[i]) { for(int j=i+1;j<nums.length;j++) { if(j==i+1||nums[j-1]!=nums[j]) { sum=nums[i]+nums[j]; Integer index=map.get(-sum); if(index !=null){ if(index>j) { list.add(Arrays.asList(nums[i],nums[j],-sum)); } } } } } } return list; } }