# 15. 3Sum

## 1. Question

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]]such thati != j,i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

## 2. Examples

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]


Example 2:

Input: nums = []
Output: []


Example 3:

Input: nums = [0]
Output: []


## 3. Constraints

• 0 <= nums.length <= 3000
• -105 <= nums[i] <= 105

## 5. Solutions

1. class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);

HashMap<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
int cnt = map.getOrDefault(num, 0);
map.put(num, cnt + 1);
}

ArrayList<List<Integer>> lists = new ArrayList<>();

for (int i = 0; i < nums.length; i++) {
if (0 != i && nums[i] == nums[i - 1]) {
continue;
}
int a = nums[i];
map.put(a, map.get(a) - 1);

for (int j = i; j < nums.length; j++) {
if (0 != j && nums[j] == nums[j - 1]) {
continue;
}

int b = nums[j];
int c = -(a + b);

if (c < b || map.getOrDefault(b, 0) <= 0) {
continue;
}
map.put(b, map.get(b) - 1);

if (map.getOrDefault(c, 0) > 0) {
ArrayList<Integer> integers = new ArrayList<>();
}

map.put(b, map.get(b) + 1);

}
map.put(a, map.get(a) + 1);
}
return lists;
}
}