LeetCode刷題筆記-15. 三數之和（雙指針法）

題目：

給你一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有滿足條件且不重複的三元組。

注意：答案中不可以包含重複的三元組。

執行個體：

給定數組 nums = [-1, 0, 1, 2, -1, -4]，

滿足要求的三元組集合為：

[

[-1, 0, 1],

[-1, -1, 2]

]

題解：

首先想到的思路是暴力法，但是三個元素周遊的話時間複雜度為O（n^3），很容易逾時，是以我們可以想到把其中一個元素固定，然後用雙指針法查找剩下數組元素中的兩個符合條件的值，這樣的話時間複雜度為O（n ^2）。

要用雙指針法我們首先需要将數組排好序，磨刀不誤砍柴工。然後周遊數組，我們周遊所找到的的元素 i 其實是是三元素中最小的元素，然後在[i+1,n-1]内用雙指針尋找剩下兩個元素，在真正的用雙指針法之前，我們在判斷num[i]時可以利用性質适當的舍去不可能存在解的情況：①如果num[i]>0,在最小元素都大于0的情況下我們不可能找到解；②如果存在重複元素，我們隻考慮該元素首次出現時的情況，避免重複解；

然後令左指針 L=i+1，右指針 R=n−1，當 L<R 時，執行循環：

當nums[i]+nums[L]+nums[R]==0，執行循環，判斷左界和右界是否和下一位置重複，去除重複解。并同時将 L,RL,R 移到下一位置，尋找新的解

若和大于 0，說明 nums[R] 太大，R左移；若和小于 0，說明 nums[L]太小，L右移。

代碼如下：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> lists=new ArrayList<>();
        int len=nums.length;
        
        if(nums==null||len<3) return lists;
        Arrays.sort(nums);
        for(int i=0;i<len-2;i++){
            if(nums[i]>0) return lists;
            if(i>0){
                if(nums[i-1]==nums[i]) continue;
            }
            int now=nums[i];
            int left=i+1,right=len-1;
            while(right>left){
                int le=nums[left],ri=nums[right];
                int sum=le+ri+now;
                if(sum==0){
                    List list=new ArrayList();
                    list.add(now);
                    list.add(le);
                    list.add(ri);
                    lists.add(list);
                    while(left<right && nums[left+1]==le) left++;
                    while(left<right && nums[right-1]==ri) right--;
                    right--;
                    left++;
                }
                else if(sum>0) right--;
                else left++;
            }
        }
        return lists;
    }
}
           

大神題解