LeetCode：15.三数之和

题目分析：需要三个数之和为0，并且不能有重复的三元组，需要特别注意如何去掉重复的

解法一：暴力**，遍历所有可能，可以使用Set集合进行去重

解法二：使用哈希表+两次遍历，a+b=-c

先将所有数据存入哈希表中，遍历的时候i和 j，查看是否找到满足要求的-(a[i]+a[j})，也要考虑去出重复问题

public List<List<Integer>> threeSum(int[] nums) {
		
		Set<List<Integer>> reulstSet = new HashSet<>();
		
		Map<Integer, Integer> map = new HashMap<>();
		for(int i=0; i< nums.length; i++) {
			map.put(nums[i], i);
		}
		
		for(int i=0; i < nums.length-1; i++) {
			for(int j=i+1; j<nums.length; j++) {
				int target = 0 - (nums[i] + nums[j]);
				if(map.containsKey(target) && !map.get(target).equals(i) && !map.get(target).equals(j)) {
					List<Integer> list = new ArrayList<>();
					list.add(nums[i]);
					list.add(nums[j]);
					list.add(target);
					list.sort(Comparator.naturalOrder());
					reulstSet.add(list);
				}
			}
		}
		
		return new ArrayList<>(reulstSet);
}

提交结果：

解法三：排序+左右下标推进

对于排完序之后的数组，移动思路类似LeetCode 11题

public static List<List<Integer>> threeSum(int[] nums) {
	Set<List<Integer>> reulstSet = new HashSet<>();
	Arrays.sort(nums);
	for(int i=0; i<nums.length; i++) {
		for(int j=i+1,k=nums.length-1; j<k; ) {
			int sumResult = nums[i] + nums[j] + nums[k];
			if(sumResult==0) {
				List<Integer> list = Arrays.asList(nums[i], nums[j], nums[k]);
				reulstSet.add(list);
				j++;
				k--;
			}
			if(sumResult<0) {
				j++;
			}
			if(sumResult>0) {
				k--;
			}
		}
	}
	return new ArrayList<>(reulstSet);
}

提交结果：