給你一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個(gè)元素 a，b，c ，使得 a + b + c = 0，請(qǐng)你找出所有和為 0 且不重復(fù)的三元組

https://leetcode-cn.com/problems/3sum/

示例1：

輸入：nums = [-1,0,1,2,-1,-4]
輸出：[[-1,-1,2],[-1,0,1]]

示例2：

輸入：nums = []
輸出：[]

示例3：

輸入：nums = [0]
輸出：[]

提示：

0 <= nums.length <= 3000
-105 <= nums[i] <= 105

Java解法

思路：

• 熟悉的遍歷算法，條件不一致，取出第一個(gè)數(shù)，遍歷剩下的數(shù)中滿足b+c=-a
• 沒那么簡(jiǎn)單，自己坑了自己，去重是不能去的，應(yīng)該要先排序的
• 先排序（熟悉了下快排），然后依次遍歷數(shù)據(jù)，注意若數(shù)據(jù)與前一位相同則需要跳過(guò)（排過(guò)序所以不用擔(dān)心需要往前找），中間要記得優(yōu)化，數(shù)據(jù)越來(lái)越大的，所以相加為0的數(shù)據(jù)必定是兩端往內(nèi)部收斂
• 存入數(shù)據(jù)忘記判斷條件，導(dǎo)致超時(shí)驗(yàn)證，自行運(yùn)行花了5秒，還是錯(cuò)的，要注意

package sj.shimmer.algorithm;

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

/**
 * Created by SJ on 2021/2/3.
 */

class D10 {
    public static void main(String[] args) {
        System.out.println(threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
        System.out.println(threeSum(new int[]{0}));
        System.out.println(threeSum(new int[]{0,0,0}));
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        ArrayList<List<Integer>> results = new ArrayList<>();
        if (nums == null || nums.length < 3) {
            return results;
        }
        quickSort(nums, 0, nums.length - 1);
        Utils.logTime();

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                break;
            }
            if (i > 0 && nums[i] == nums[i-1]) {
                continue;
            }
            int k = nums.length-1;
            for (int j = i + 1; j < nums.length; j++) {
                if (j > i + 1 && nums[j] == nums[j-1]) {
                    continue;
                }
                //定了唯一的 i,j  就只有唯一的k
                while (j<k&&nums[i] +nums[j] +nums[k]>0){
                    k--;
                }
                if (j==k) {
                    //這一輪再也查不到了
                    break;
                }
                if (nums[i] +nums[j] +nums[k]==0) {
                    List<Integer> integers = new ArrayList<>();
                    integers.add(nums[i]);
                    integers.add(nums[j]);
                    integers.add(nums[k]);
                    results.add(integers);
                }
            }
        }

        return results;
    }


    private static int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            //找到基準(zhǔn)交換后的位置、作為下次分割邊界
            int spiltIndex = findPonitIndex(arr, left, right);
            quickSort(arr, left, spiltIndex - 1);
            quickSort(arr, spiltIndex + 1, right);
        }
        return arr;
    }

    private static int findPonitIndex(int[] arr, int left, int right) {
        int point = arr[left];//以左邊界為比較基準(zhǔn)值
        while (left < right) {
            //以左為基準(zhǔn)，先從右側(cè)遍歷,小于基準(zhǔn)交互
            while (point <= arr[right] && left < right) {
                right--;
            }
            if (left < right) {
                //未相遇, 第一個(gè)左側(cè)值是基準(zhǔn)，已被記錄
                arr[left] = arr[right];
            }
            //左側(cè)遍歷,大于基準(zhǔn)跳出
            while (point > arr[left] && left < right) {
                left++;
            }
            if (left < right) {
                //未相遇, 第一個(gè)右側(cè)值移至原基準(zhǔn)位置，已被記錄
                arr[right] = arr[left];
            }
        }
        arr[left] = point;
        return left;
    }
}

image

官方解

1. 排序 + 雙指針

   我參考的就是這種寫法，但他們排序用的直接是Arrays.sort(nums);

   官方解優(yōu)化了三重循環(huán)的第二次與第三次，因?yàn)橛行?，且結(jié)果固定，所以用雙指針優(yōu)化了該嵌套

   • 時(shí)間復(fù)雜度： O(N2)，其中 N 是數(shù)組 nums 的長(zhǎng)度
   • 空間復(fù)雜度：O(logN)。忽略存儲(chǔ)答案的空間，額外的排序的空間復(fù)雜度為O(logN)。然而我們修改了輸入的數(shù)組 nums，在實(shí)際情況下不一定允許，因此也可以看成使用了一個(gè)額外的數(shù)組存儲(chǔ)了 nums 的副本并進(jìn)行排序，空間復(fù)雜度為 O(N)