[数据结构与算法]Leetcode015(三数之和)

地址：

https://leetcode-cn.com/problems/3sum/

解法一（暴力求解）————超出时间限制：

	 List<List<Integer>> threeSum=new ArrayList<>();//存放结果
		 if(nums.length<3) return null;//假如数组长度不足3，肯定没有三个数相加为0
		 for(int i=0;i<nums.length-2;i++) {
			 for(int j=i+1;j<nums.length-1;j++) {
				 for(int k=j+1;k<nums.length;k++) {
					 if(nums[i]+nums[j]+nums[k]==0) {
						 List <Integer> temp=new ArrayList<>();
						 //将这三个数加到temp中
						 temp.add(nums[i]);
						 temp.add(nums[j]);
						 temp.add(nums[k]);
						 Collections.sort(temp);//将temp进行升序排序
						//判断是否出现重复
						 if(!threeSum.contains(temp)) {
							 threeSum.add(temp);
						 }
					 }
				 }
			 }
		 }//for
		return threeSum;

解法二（排序+双指针）：

题解：

https://leetcode-cn.com/problems/3sum/solution/hua-jie-suan-fa-15-san-shu-zhi-he-by-guanpengchn/

实现思路：

首先对数组进行排序，排序后固定一个数 nums[i]，再使用左右指针指向 nums[i]后面的两端，数字分别为 nums[L] 和 nums[R]，计算三个数的和 sum 判断是否满足为 0，满足则添加进结果集
如果 nums[i]大于 0，则三数之和必然无法等于 0，结束循环
如果 nums[i] == nums[i?1]，则说明该数字重复，会导致结果重复，所以应该跳过

当?sum==0时，L++，R--；
假如当 sum == 0 时，nums[L] == nums[L+1] 则会导致结果重复，应该跳过，L++
假如当 sum == 0 时，nums[R]== nums[R?1] 则会导致结果重复，应该跳过，R??
时间复杂度：O(n^2)，n 为数组长度

代码：

 public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
     int len = nums.length;
     if(nums == null || len < 3) return ans;
     Arrays.sort(nums); // 排序
     for (int i = 0; i < len ; i++) {
         if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
         if(i > 0 && nums[i] == nums[i-1]) continue; // 跳出此层循环不执行，i++
         int L = i+1;
         int R = len-1;
         while(L < R){
             int sum = nums[i] + nums[L] + nums[R];
             if(sum == 0){
                 ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
                 //假如这里不加L<R，那么遇到nums={0,0,0}这种情况时，L会一直加到末尾
                 while ( L<R&&nums[L] == nums[L+1]) L++; // 去重
                 while ( L<R&&nums[R] == nums[R-1]) R--; // 去重
                 L++;
                 R--;
             }
             else if (sum < 0) L++;
             else if (sum > 0) R--;
         }
     }
     return ans;
	}