Leetcode: hash table 07 (sum of three numbers)

The first 15 topic . Sum of three numbers

Force button topic link

Give you one containing n Array of integers nums, Judge nums Are there three elements in a,b,c , bring a + b + c = 0 ？ Please find out all the triples that meet the conditions and do not repeat .

Be careful ： Answer cannot contain duplicate triples .

Example ：

Given array nums = [-1, 0, 1, 2, -1, -4],

The set of triples satisfying the requirement is ：
[
[-1, 0, 1],
[-1, -1, 2]
]

This question ... To give up , Look at the solution . Ninety five percent of the tests passed , It shows that the idea is correct , It's just a timeout . Can't , The test sample is too long .

package com.programmercarl.hashtable;

import java.util.*;

/** * @ClassName sum3 * @Descriotion TODO * @Author nitaotao * @Date 2022/6/21 15:03 * @Version 1.0 **/
public class sum3 {
    
  
    public static List<List<Integer>> threeSum(int[] nums) {
    
        /** *  Still usable hashmap, *  Sum of three numbers , In fact, when the current two numbers are determined , The last number has been fixed . *  You can get the first two numbers to , Then calculate the last number , To prevent the same , Three number sort as key  */
        List<List<Integer>> result = new ArrayList<>();
        int temp;
        HashMap<String, String> map = new HashMap<>();
        for (int i = 0; i < nums.length - 2; i++) {
    
            for (int j = i + 1; j < nums.length - 1; j++) {
    
                // The third number 
// temp = 0 - nums[i] - nums[j];
                temp = -(nums[i] + nums[j]);
                // Three number order , Descending 
                String key = order3(nums[i], nums[j], temp);
                map.put(key, i + "#" + j + "=" + temp);
            }
        }
        // Only what has appeared is correct 
        Set<String> set = new HashSet<>();
        Set<String> keys = map.keySet();
        for (String key : keys) {
    
            for (int i = 0; i < nums.length; i++) {
    
                // value 
                String valStr = map.get(key);
                // The value currently being compared , Not necessarily 
                int value = Integer.parseInt(valStr.split("=")[1]);
                if (value == nums[i]) {
    
                    // Then judge whether this number is your own 
                    // If not , Add again 
                    // Position comparison 
                    // Location 
                    String[] pos = valStr.split("=")[0].split("#");
                    if (!(pos[0].equals(String.valueOf(i)) || pos[1].equals(String.valueOf(i)))) {
    
                        set.add(key);
                    }
                }
            }
        }
        // Processing result set , duplicate removal 
        for (String res : set) {
    
            List<Integer> resultList = new ArrayList<>();
            String[] split = res.split("#");
            resultList.add(Integer.valueOf(split[0]));
            resultList.add(Integer.valueOf(split[1]));
            resultList.add(Integer.valueOf(split[2]));
            result.add(resultList);
        }
        return result;
    }

    /** *  Sort by three numbers in descending order  * * @param nums1 * @param nums2 * @param nums3 * @return */
    public static String order3(int nums1, int nums2, int nums3) {
    
        if (nums1 > nums2) {
    
            if (nums1 > nums3) {
    
                //nums1 Maximum 
                if (nums2 > nums3) {
    
                    return "" + nums1 + "#" + nums2 + "#" + nums3;
                } else {
    
                    return "" + nums1 + "#" + nums3 + "#" + nums2;
                }
            } else {
    
                //nums1 no nums3 Big 
                return "" + nums3 + "#" + nums1 + "#" + nums2;
            }
        } else {
    
            //nums2>nums1
            if (nums2 > nums3) {
    
                if (nums1 > nums3) {
    
                    return "" + nums2 + "#" + nums1 + "#" + nums3;
                } else {
    
                    return "" + nums2 + "#" + nums3 + "#" + nums1;
                }
            } else {
    
                //nums1 Maximum 
                return "" + nums3 + "#" + nums2 + "#" + nums1;
            }
        }
    }
}

My idea is to use hashmap do
Sum of three numbers , In fact, when the current two numbers are determined , The last number has been fixed .
You can get the first two numbers to , Then calculate the last number , To prevent the same , Three number sort as key
To prevent key duplication , Sort the elements first , In the key , The composition of the value is The position of the first element # The position of the second element = The value of the required element .
The symbol is simply marked as .
Because the two values determine , The third value has been determined , Whether there is or not , Save it first .
Go over it again , See if the third value is , If there is , And the position is not the value of the first two elements , The sequence is found successfully .

==============================================================================
hhhhh
I'm looking at the solution , I need to read my ID number .

It's been a hard day .
1： If the array length <3 Go straight back to .
2： Array sorting , Ascending .
3： Starting from the first place , Create the first element on the right as the left pointer , The last element is the right pointer .
4： If the first element >0, The smallest element >0, Go straight back , Without looking at the .
5： If except for the first element , The next benchmark element is the same as the previous one , Then skip , Because the results repeat .
6： Take the base element as the first sum , Then the second and third sums , From the left pointer and the right pointer respectively .
7： The transformation law of the left and right pointers is similar to that of the reference elements , Do not repeat with your last element , Otherwise, the result will be repeated .
8： To the left 、 The right is different from the last one , according to sum Value carry of , value >0, Then subtract a little from the right , value <0, Add a dot to the left , After all, it is in ascending order . Until the left and right coincide , End of cycle .
9： The datum element keeps moving back .

    public static List<List<Integer>> threeSum(int[] nums) {
    
        List<List<Integer>> result = new ArrayList<>();
        // Length of array 
        int len = nums.length;
        // When the length of the array is less than 3 when , immediate withdrawal 
        if (len < 3) {
    
            return result;
        }
        // Sort the array , Ascending 
        Arrays.sort(nums);
        for (int i = 0; i < len; i++) {
    
            // If the starting element of the traversal is greater than 0, You just quit 
            // Because it's ascending , Indicates that the minimum values are greater than 0, End directly 
            if (nums[i] > 0) {
    
                break;
            }
            // duplicate removal , When the starting value is equal to the previous element , Then the result will be the same as the previous one .
            /** *  Such as  -1 -1 2 *  Just calculate the first -1 Of , Will put the second -1 Included in  *  Then take the second -1 When calculating , The first one is repeated in the multi substitution . */
            if (i > 0 && nums[i] == nums[i - 1]) {
    
                continue;
            }
            // Left pointer 
            int left = i + 1;
            // Right pointer 
            int right = len - 1;
            // When left is not equal to right 
            while (left < right) {
    
                // Add three numbers 
                int sum = nums[i] + nums[left] + nums[right];
                // If it is equal to 0, Then add the result set 
                if (sum == 0) {
    
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // When moving the left and right pointers , First, judge the values of the left and right pointers , Skip if repeated 
                    while (left < right && nums[left] == nums[left + 1]) {
    
                        left++;
                    }
                    // duplicate removal , because  i unchanged , When this time  r  The value of the fetched number is the same as the previous one , So there is no need to calculate 
                    while (left < right && nums[right] == nums[right - 1]) {
    
                        right--;
                    }
                    // When the left and right sides are not the same as the previous one 
                    left++;
                    right--;
                } else if (sum < 0) {
    
                    left++;
                } else if (sum > 0) {
    
                    right--;
                }
            }
        }
        return result;
    }