leetcode 第15题 <3Sum>(java)

题面

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: The solution set must not contain duplicate triplets. For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]

题解

矢量S里面找所有3个和为零的数。 最容易想到的是3重循环所有的元素。 但是下面的方案做了一些改进：

先对数据进行排序。这样可以过滤掉一些一定大于零的值借助map避免第三层遍历

code

public class Solution { public List<List<Integer>> threeSum(int[] nums) { List<Integer> array=new ArrayList<>(); List<List<Integer>> result=new ArrayList<>(); Arrays.sort(nums); HashMap<Integer,List<Integer>> map=new HashMap<>(); for(int i=0;i<nums.length;i++){ List<Integer> index=new ArrayList<>(); if(map.get(nums[i])==null){ index.add(i); map.put(nums[i],index); } else{ map.get(nums[i]).add(i); } }//把数组nums储存到hashmap中 for(int i=0;i<nums.length-2;i++){ if(nums[i]>0){ break; } if(i>0&&nums[i]==nums[i-1]){ continue; } for(int j=i+1;j<nums.length-1;j++){ int numtest=-nums[i]-nums[j]; if(numtest<nums[j]){//如果要找的数比nums[j]还小，后面不可能找到了 break; } if(j>i+1&&nums[j]==nums[j-1]){ continue; } List<Integer> anss=map.get(numtest); if (anss==null){ continue; } else{ for(Integer ans:anss){ List<Integer> a=new ArrayList<>(); if(ans!=i&&ans!=j){ a.add(nums[i]); a.add(nums[j]); a.add(nums[ans]); result.add(a); break; } } } } } return result; } }