Three sum] [LeetCode | punch brush

Has been the habit of brush, recently saw the nuggets held a brush activities, especially to participate in! This is question 8. I have to say the nuggets theme is beautiful! Praise.

This article is participating in the nuggets team online activity, clickCheck spring recruitment positions in big factories

I. Title Description:

The sum of three number

describe

Given an array S with n integers, find three integers A, b, and c in S, and find all triples such that a + b + c = 0. The result cannot contain duplicate triples.

Case 1:

Input :[2,7,11,15] output :[]Copy the code

Example 2:

Input :[-1,0,1,2,-1,-4] Output :[[-1, 0,1],[-1, -1, 2]Copy the code

Ii. Analysis of Ideas:

Iii. AC Code:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/* * @lc app=leetcode.cn id=15 lang= Java * * [15] Sum of three digits */

// @lc code=start
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        // fix bug i < nums.length ,not result.size
        for (int i = 0; i < nums.length; i++) {
            if(i ! =0 && nums[i] == nums[i - 1]) {
                continue;
            }
            findTwoNum(nums, i, result);
        }
        return result;
    }

    private void findTwoNum(int[] nums, int index, List<List<Integer>> result) {
        // why [left+1,length-1]
        // finaly nums[left+1-1]==nums[left+]
        int left = index + 1;
        int right = nums.length-1;
        int target = -nums[index];
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum < target) {
                left++;
            } else if (sum > target) {
                right--;
            } else {
                // sum = target
                List<Integer> list = new ArrayList();
                list.add(nums[index]);
                list.add(nums[left]);
                list.add(nums[right]);
                // result.add
                result.add(list);
                left++;
                right--;
                // nums[index]==nums[index+1]
                while (left < right && nums[left] == nums[left - 1]) {
                    left++;
                }
            }
        }
    }

}
// @lc code=end

Copy the code

Iv. Summary:

This is already the 8th question of the sum of two numbers, from the first question to see friends, has been able to quickly react to what this question is looking at, this problem is the 8th question using double Pointers can quickly solve the problem.

What is the difference between the sum of two numbers and the sum of three numbers?

A: No difference.

[j]. Int I, int I, int I, int I

How do I substitute the sum of three numbers? A + b + c= 0 and then b + C = -a

So how do we do a plus b plus c is equal to 3? b + c= 3 – a