# leetcode解题方案--015--3 sum

xiaoxiao2021-02-28  6

### 题目

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] ]

### 分析

class Solution { public List<List<Integer>> threeSum(int[] nums) { HashSet<List<Integer>> set = new HashSet<>(); List<List<Integer>> list = new ArrayList<>(); for (int i = 0; i < nums.length; i++) { Map<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int k = i + 1; k < nums.length; k++) { if (map.containsKey(nums[k])) { List<Integer> tmpList = new ArrayList<>(); tmpList.add(nums[i]); tmpList.add(nums[k]); tmpList.add( 0 - nums[i] - nums[k]); Collections.sort(tmpList); set.add(tmpList); } else { map.put(0 - nums[i] - nums[k], k); } } } list.addAll(set); return list; } }

public static List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); List<List<Integer>> list = new ArrayList<>(); for (int i = 0; i < nums.length - 2; i++) { if (i == 0 || (i > 0 && nums[i] != nums[i-1])) { int k1 = i + 1; int k2 = nums.length - 1; while (k2-k1>=1) { if (nums[i] + nums[k1] + nums[k2] == 0) { list.add(Arrays.asList(nums[i], nums[k1], nums[k2])); while (k1 < k2 && nums[k1] == nums[k1+1]) k1++; while (k1 < k2 && nums[k2] == nums[k2-1]) k2--; k1++;k2--; } else if (nums[i] + nums[k1] + nums[k2] > 0) { k2--; }else { k1++; } } } } return list; }