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

4. References

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/3sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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<>();
                    integers.add(a);
                    integers.add(b);
                    integers.add(c);
                    lists.add(integers);
                }
   
                map.put(b, map.get(b) + 1);
   
            }
            map.put(a, map.get(a) + 1);
        }
        return lists;
    }
   }