一.題目描述

給你一個整數(shù)數(shù)組?nums，判斷是否存在三元組?[nums[i], nums[j], nums[k]]滿足?i != j、i != k且?j != k，同時還滿足?nums[i] + nums[j] + nums[k] == 0。請你返回所有和為?0且不重復(fù)的三元組。

創(chuàng)新互聯(lián)公司是一家專注于成都網(wǎng)站設(shè)計、網(wǎng)站制作與策劃設(shè)計,渦陽網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)公司做網(wǎng)站,專注于網(wǎng)站建設(shè)十多年,網(wǎng)設(shè)計領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:渦陽等地區(qū)。渦陽做網(wǎng)站價格咨詢:18980820575

注意：答案中不可以包含重復(fù)的三元組，數(shù)字可以相同，但是數(shù)組下標不能相同。

二.題目示例

示例一：

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

示例二：

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

示例三：

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

三.解題分析

本題采用排序和雙指針的解法：

?題目中指出需要尋找三個不同的并且和為0的三元組，所以我們需要用到三個循環(huán)并且每次遍歷的元素都要比前一次遍歷少一個元素。因為第一次遍歷以第一個數(shù)為基點，去尋找第二個元素，然后確定好前兩個元素后再去尋找第三個元素，另外兩個需在除第一次遍歷確定的元素以外剩下的數(shù)組中找出才不算有重復(fù)元素（第二次遍歷同理）。此時需要用到三個循環(huán)來確定三個元素才得以完成，時間復(fù)雜度為 ，那么我們應(yīng)該怎么減小時間復(fù)雜度呢？

減少時間復(fù)雜度可以通過減少循環(huán)來解決，由上面知需要一個一個的尋找元素來確定是否其和為0，減少時間復(fù)雜度就需要減少尋找一個元素的循環(huán)，那我們就可以定一變二。

例：當確定第一個元素時n1時，另外兩個元素n2和n3和就為-n1；即為一個不變值；當n2增大時n3減小，當n2減小時n3增大

這樣我們就可以 在確定第一個元素后，運用雙指針來同時確定第二個和第三個元素的值。因為需要判斷增大減小，就必須先給數(shù)組排序運用sort即可。

基本步驟：

1.將數(shù)組由小到大排序? ??

2.利用for循環(huán)枚舉第一個元素? ? ?

3.確定第三個元素指針位置? ? ?

4.枚舉第二個元素并尋找是否存在第三個元素滿足條件

?每一步都需要判斷兩數(shù)之和是大于-n1還是小于-n1，若大于則移動第三個元素指針，若小于則移動第二個元素指針；當兩個指針相等時則代表無解。

5.將三個元素存入三元組并返回? ? ?vector>

以[2,5,3,-5,-1,4]數(shù)組為例演示雙指針移動過程，排序好的數(shù)組如下圖：

橙色區(qū)域為確定好的第一個元素，紫色指針指向第二個元素，紅色指針指向第三個元素

這樣我們可以清楚的了解雙指針移動的判斷條件對應(yīng)的移動位置了。

萬事俱備，只欠東風(fēng)！讓我為大家講解(注：僅為講解代碼，幫助家人們理解）一下代碼吧！

class Solution {
public:
    vector>threeSum(vector& nums) {
     sort(nums.begin(),nums.end());//先給代碼排序
     int n=nums.size();//用n來代替數(shù)組的大小
     vector>sum;//創(chuàng)建一個數(shù)組，用來存放三元組
     //枚舉第一個元素，第一層循環(huán)需要全部遍歷
     for(int i=0;i0&&nums[i]==nums[i-1]) continue;
        //確定第三個元素指針
        int c=n-1;
        int target=-nums[i];//后兩個元素和
        //枚舉第二個元素
        for(int b=i+1;bi+1&&nums[b]==nums[b-1]) continue;
            //判斷指針移動條件
            while(btarget){
                c--;
            }
            if(b==c)break;//若兩個指針相等了還無解，就不用再比下去了
            //如果三個元素和為0，則加入三元組中
            if(nums[b]+nums[c]==target){
                sum.push_back({nums[i],nums[b],nums[c]});
            }
        }
    }
    return sum;//輸出三元組
    }
};

當我們需要確定多個元素時，若要減小時間復(fù)雜度則可以采用指針的方法同時進行操作不需要嵌套。好啦，這道題就講解完成了，以后我也會多多更新的，歡迎大家持續(xù)關(guān)注我喲！

??

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

新聞名稱：力扣15題——三數(shù)之和C++講解-創(chuàng)新互聯(lián)
網(wǎng)頁網(wǎng)址：http://sd-ha.com/article44/jjghe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App開發(fā)、網(wǎng)站設(shè)計、用戶體驗、企業(yè)建站、網(wǎng)站排名、域名注冊

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)