This is the fifth day of my participation in the August More text Challenge. For details, see:August is more challenging

Topic describes

Given an array of n integers, nums, determine if there are three elements a, b, and c in NUMs such that a + b + c = 0? Find all triples that sum 0 and are not repeated.

Note: Answers may not contain duplicate triples.

Example 1: input: nums = [1, 2, 1, 4] output: [[1, 1, 2], [1, 1]] source: the power button (LeetCode) link: https://leetcode-cn.com/problems/3sum copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.Copy the code

Thought analysis

• Sum of three is an array type problem, which is also an advanced version of the sum of two numbers.
• For array problems, sorting array elements can simplify the thinking and improve the efficiency of the algorithm.
• Another difficulty with this problem is that it is not allowed to contain duplicate triples. For each level of the loop, adjacent elements cannot be the same.

code

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < n; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                for (int k = j + 1; k < n; k++) {
                    if (k > j + 1 && nums[k] == nums[k - 1]) {
                        continue;
                    }
                    int tempSum = nums[i] + nums[j] + nums[k];
                    if (tempSum > 0) {
                        break;
                    } else if (tempSum == 0) {
                        List<Integer> temp = newArrayList<>(); temp.add(nums[i]); temp.add(nums[j]); temp.add(nums[k]); ans.add(temp); }}}}returnans; }}Copy the code

• This is the implementation code for the three-layer loop, which shows a timeout at the time of submission and fails. Set -nums[I] to target, and then use double Pointers to iterate through the array from the beginning to the end to get the answer.

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int target = -nums[i];
            int k = n - 1;
            for (int j = i + 1; j < n; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                while (j < k && nums[j] + nums[k] > target) {
                    k--;
                }
                if (j == k) {
                    break;
                }
                int tempSum = nums[i] + nums[j] + nums[k];
                if (tempSum == 0) {
                    List<Integer> temp = newArrayList<>(); temp.add(nums[i]); temp.add(nums[j]); temp.add(nums[k]); ans.add(temp); }}}returnans; }}Copy the code

conclusion

• The time complexity by code is order n by n, quicksort uses extra space, order log n space complexity.
• This is a classic topic, done before, but failed this time, to summarize more, more reflection, master this topic.
• Stick to a daily question, come on!