Leetcode topic analysis 3sum

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：

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• 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) ``` analysis ：

Sort the array ;

start from 0 To n-1, Yes numstart Find the other two numbers , Here we use mid and end;

mid Point to start+1,q Point to the end .sum = numstart + nummid+ numend;

Use the forcing theorem to solve , The termination condition is mid == end;

Incidental weight removal

duplicate removal ：

If start here we are start+1,numstart == numstart - 1, Then the solution must be repeated ;

If mid++,nummid = nummid - 1, Then the solution must be repeated .

    public List<List<Integer>> threeSum(int[] nums) {
        if (nums == null || nums.length < 3) {
            return new ArrayList<List<Integer>>();
        }
        Set<List<Integer>> set = new HashSet<List<Integer>>();
        Arrays.sort(nums);
        for (int start = 0; start < nums.length; start++) {
            if (start != 0 && nums[start - 1] == nums[start]) {
                continue;
            }
            int mid = start + 1, end = nums.length - 1;
            while (mid < end) {
                int sum = nums[start] + nums[mid] + nums[end];
                if (sum == 0) {
                    List<Integer> tmp = new ArrayList<Integer>();
                    tmp.add(nums[start]);
                    tmp.add(nums[mid]);
                    tmp.add(nums[end]);
                    set.add(tmp);
                    while (++mid < end && nums[mid - 1] == nums[mid])
                        ;
                    while (--end > mid && nums[end + 1] == nums[end])
                        ;
                }
                else if (sum < 0) {
                    mid++;
                }
                else {
                    end--;
                }
            }
        }
        return new ArrayList<List<Integer>>(set);
    }