題目

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

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

A solution set is:
[ [-1, 0, 1], [-1, -1, 2] ]

分析

這道題目是求三個(gè)數(shù)組之和為0寇漫，分兩種情況守呜，一種是三個(gè)數(shù)字全是0液南，一種是三個(gè)數(shù)字有正有負(fù)才成立岸蜗，
當(dāng)前數(shù)組是無(wú)序的裙戏，我們可以考慮對(duì)數(shù)組排序绞旅；
首先可以通過(guò)三層循環(huán)嵌套的暴力方式解決姆打，時(shí)間復(fù)雜度為O(n^3)沧卢，這里不做討論鲫懒；
通過(guò)分析嫩实，我們可以將第一個(gè)數(shù)字的相反數(shù)設(shè)為目標(biāo)數(shù)target，后面的兩個(gè)數(shù)字之和只要等于target就成立窥岩，反之不成立甲献；
遍歷這個(gè)有序數(shù)組，取出target颂翼，遍歷長(zhǎng)度為len-2晃洒，因?yàn)橐粝聝蓚€(gè)數(shù)字和target相加，在遍歷過(guò)程中朦乏，我們需要對(duì)當(dāng)前數(shù)字進(jìn)行處理球及，如果大于0，說(shuō)明以后的數(shù)字都是大于0的呻疹，不會(huì)出現(xiàn)三數(shù)之和等于0的情況吃引，直接跳出返回list，從第二個(gè)數(shù)字開(kāi)始诲宇，如果之前出現(xiàn)過(guò)际歼，需要跳過(guò)重復(fù)數(shù)字；
設(shè)置左右兩個(gè)指針姑蓝，左指針為當(dāng)前數(shù)字的下一個(gè)數(shù)字鹅心，右指針為數(shù)組最后一個(gè)數(shù)字，遍歷截取的數(shù)組纺荧，如果左右兩個(gè)指針之和等于target旭愧，就代表尋找到了一組颅筋，繼續(xù)尋找下一組，左指針加一输枯，右指針減一议泵，左右指針也需要跳過(guò)重復(fù)數(shù)字，當(dāng)左指針大于等于右指針時(shí)桃熄，跳出當(dāng)前循環(huán)先口。

代碼

public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList<>();
        int left,right;//左右指針
        for (int i = 0; i < nums.length - 2; i++) {
            //如果數(shù)字大于0，直接跳出循環(huán)
            if (nums[i] > 0) {
                break;
            }
             //數(shù)字重復(fù)處理
            if (i > 0 && nums[i - 1] == nums[i]) {
                continue;
            }
            left= i + 1;
            right = nums.length - 1;
            while (left < right) {
                if (nums[left] + nums[right] == -nums[i]) {//滿足條件
                    List<Integer> l = new ArrayList<>();
                    l.add(nums[i]);
                    l.add(nums[left]);
                    l.add(nums[right]);
                    list.add(l);
                    left++;
                    right--;
                    //左指針重復(fù)處理
                    while (left< right&& nums[left] == nums[left- 1]) {
                        left++;
                    }
                    //右指針重復(fù)處理
                    while (left< right&& nums[right] == nums[right+ 1]) {
                        right--;
                    }
                } else if (nums[left] + nums[right] > -nums[i]) {
                    right-= 1;
                } else {
                    left+= 1;
                }
            }
        }
        return list;
    }