【leetcode刷題】21.三數之和——Java版

前言

哈喽，大家好，我是一條。

糊塗算法，難得糊塗

現在遇題就想「動态規劃」和「雙指針」

Question

15. 三數之和

難度：中等

給你一個包含 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      

Solution

在這之前，我們做過兩數之和。根據動态規劃的思想，将問題拆解成一個數與另兩個數的和互為相反數。

再利用雙指針，計算另兩數之和。

為了不得到重複解，先對數組進行排序。

首先對數組按升序進行排序，排序後固定一個數 ，再使用左右指針指向該數後面的兩端，計算三個數的和是否為 0，滿足則添加進結果集

考慮幾種可能有重複解的情況

對于重複元素：跳過，避免出現重複解

等于0時，判斷邊界是否和下一個值重複，去除重複解

Code

所有leetcode代碼已同步至github

歡迎star

/**
 * @author yitiaoIT
 */

class Solution {
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList();
        int len = nums.length;
        if(nums == null || len < 3) return ans;
        Arrays.sort(nums); // 排序
        for (int i = 0; i < len ; i++) {
            if(nums[i] > 0) break; // 如果目前數字大于0，則三數之和一定大于0，是以結束循環
            if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
            int L = i+1;
            int R = len-1;
            while(L < R){
                int sum = nums[i] + nums[L] + nums[R];
                if(sum == 0){
                    ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
                    while (L<R && nums[L] == nums[L+1]) L++; // 去重
                    while (L<R && nums[R] == nums[R-1]) R--; // 去重
                    L++;
                    R--;
                }
                else if (sum < 0) L++;
                else if (sum > 0) R--;
            }
        }        
        return ans;
    }
}
      

Result

複雜度分析

• 時間複雜度：O(N)

🌈尋寶

⭐今天是堅持刷題更文的第21/100天

⭐各位的點贊、關注、收藏、評論、訂閱就是一條創作的最大動力

⭐更多算法題歡迎關注專欄《leetcode》

為了回饋各位粉絲，禮尚往來，給大家準備了一條多年積累下來的優質資源，包括 學習視訊、面試資料、珍藏電子書等

怎麼領取請大家自己找，尋寶遊戲現在開始。

找不到可以評論留言，一條就會注意到你。

如果還不行，請私信我。