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;
     }
    }
    
Copyright © rootwhois.cn 2021-2022 all right reserved,powered by GitbookFile Modify: 2022-11-26 20:03:31

results matching ""

    No results matching ""