LeetCode_數組_中等_15.三數之和

目錄

• 1.題目
• 2.思路
• 3.代碼實作（Java）

1.題目

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

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

示例 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

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/3sum

2.思路

（1）暴力窮舉法

其思想是使用三層for循環，窮舉所有可能的情況，将符合題目條件的及結果儲存到res中。由于該方法的時間複雜度較高，是以在LeetCode上送出時會顯示超出時間限制的提示。值得注意的是在查找的過程中要去掉重複的三元組。

（2）排序+雙指針法

先對數組進行排序，可以直接使用Java中内置的方法或者自己編寫排序算法。然後周遊數組中的第1~n-2個元素nums[i]，若該元素大于0，則說明後面不存在符合題目條件的三元組，直接退出循環。否則與之前的題目兩數之和類似，采用雙指針法，查找在nums[i]之後是否存在和為-nums[i]的兩個元素。在查找的過程中要注意去掉重複的三元組。

3.代碼實作（Java）

//（1）暴力窮舉法
public List<List<Integer>> threeSum(int[] nums) {
    //對數組進行排序
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    for(int i=0; i<nums.length-2; i++){
        //如果在排序後找的第一個元素為正數，則說明不存在符合題目條件的三元組
        if(nums[i]>0) break;
        //剪枝操作
        if(nums[i]+nums[i+1]+nums[i+2]>0) break;
        if(nums[i]+nums[nums.length-1]+nums[nums.length-2]<0) continue;
        //在排序後，條件nums[i] == nums[i-1]的目的是防止包含重複的三元組
        if(i>0 && nums[i]==nums[i-1]) continue;
        for(int j=i+1;j<nums.length-1;j++){
        	//剪枝操作
        	if(nums[i]+nums[j]+nums[j+1]>0) break;
       	 	if(nums[i]+nums[j]+nums[nums.length-1]<0) continue;
            //去掉重複的三元組
            if(j>i+1 && nums[j]==nums[j-1]) continue;
            for(int k=j+1;k<nums.length;k++){
            	//剪枝操作
        		if(nums[i]+nums[j]+nums[k]>0) break;
       	 		if(nums[i]+nums[j]+nums[nums.length-1]<0) continue;
                //去掉重複的三元組
                if(k>j+1 && nums[k]==nums[k-1]) continue;
                if(nums[i]+nums[j]+nums[k]==0){
                    res.add(new ArrayList<>(Arrays.asList(nums[i],nums[j],nums[k])));
                }
            }
        }
    }
    return res;
}
           

//（2）排序+雙指針法
public List<List<Integer>> threeSum(int[] nums) {
    //對數組進行排序
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    for(int k = 0; k < nums.length - 2; k++){
        //如果在排序後找的第一個元素為正數，則說明後面不存在符合題目條件的三元組
        if(nums[k] > 0) break;
        //剪枝操作
        if(nums[k]+nums[k+1]+nums[k+2]>0) break;
        if(nums[k]+nums[nums.length-1]+nums[nums.length-2]<0) continue;
        //在排序後，條件nums[k] == nums[k-1]的目的是防止包含重複的三元組
        if(k>0 && nums[k] == nums[k-1]) continue;
        int i=k+1, j=nums.length-1;
        while(i < j){
            int sum = nums[k] + nums[i] + nums[j];
            if(sum<0){
                while(i < j && nums[i] == nums[++i]);
            }else if(sum>0) {
                while(i < j && nums[j] == nums[--j]);
            }else{
                //将找到的三元組儲存起來
                res.add(new ArrayList<>(Arrays.asList(nums[k],nums[i],nums[j])));
                while(i < j && nums[i] == nums[++i]);
                while(i < j && nums[j] == nums[--j]);
            }
        }
    }
    return res;
}