給妳壹個包含n個整數的數組nums,判斷nums中是否存在三個元素a,b,c,使得a+b+c=0?請妳找出所有和為0且不重復的三元組。
註意: 答案中不可以包含重復的三元組。
輸入: nums = [-1,0,1,2,-1,-4]
輸出: [[-1,-1,2],[-1,0,1]]
我們其實可以將這道題轉化為LeetCode兩數之和那道題,具體做法如下:
前提條件,我們需要將數組排序。
首先,外層遍歷,作為第壹個數first,並且將目標數target設置為-nums[first]。
接下來,我們只需要兩個雙指針second與third,分別指向first+1與最後壹個數,兩個指針隨著遍歷向中靠攏。如果nums[second]+nums[third]>target,那麽third就左移,否則,second就左移。而second是隨著內層遍歷而增加的。
因為我們事先將數組進行了排序,所以當內層循環達到second=third時依然找不到答案,那麽就跳過內層循環,直接遍歷下壹個first。
復雜度分析