015. 三數之和 | Leetcode題解

2021-03-02 前端布道師
題目描述

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

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

示例：

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

滿足要求的三元組集合為：
\[
  \[-1, 0, 1\],
  \[-1, -1, 2\]
\]
難度：支持語言：JavaScript、Python、C++相關標籤相關企業思路
採用分治的思想找出三個數相加等於 0，我們可以數組依次遍歷，每一項 a[i]我們都認為它是最終能夠用組成 0 中的一個數字，那麼我們的目標就是找到剩下的元素（除 a[i]）兩個相加等於-a[i].
通過上面的思路，我們的問題轉化為了給定一個數組，找出其中兩個相加等於給定值，我們成功將問題轉換為了另外一道力扣的簡單題目1. 兩數之和。這個問題是比較簡單的， 我們只需要對數組進行排序，然後雙指針解決即可。加上需要外層遍歷依次數組，因此總的時間複雜度應該是 O(N^2)。
15.3-sum在這裡之所以要排序解決是因為， 我們算法的瓶頸在這裡不在於排序，而在於 O(N^2)，如果我們瓶頸是排序，就可以考慮別的方式了。思路2首先對數組進行排序，排序後固定一個數 nums[i]nums[i]nums[i]，再使用左右指針指向 nums[i]nums[i]nums[i]後面的兩端，數字分別為 nums[L]nums[L]nums[L] 和 nums[R]nums[R]nums[R]，計算三個數的和 sumsumsum 判斷是否滿足為 000，滿足則添加進結果集如果 nums[i]nums[i]nums[i]大於 000，則三數之和必然無法等於 000，結束循環如果 nums[i]nums[i]nums[i] == nums[i−1]nums[i-1]nums[i−1]，則說明該數字重複，會導致結果重複，所以應該跳過當 sumsumsum == 000 時，nums[L]nums[L]nums[L] == nums[L+1]nums[L+1]nums[L+1] 則會導致結果重複，應該跳過，L++L++L++當 sumsumsum == 000 時，nums[R]nums[R]nums[R] == nums[R−1]nums[R-1]nums[R−1] 則會導致結果重複，應該跳過，R−−R--R−−時間複雜度：O(n2)O(n^2)O(n2)，nnn 為數組長度關鍵點解析複雜度分析代碼JavaScript 實現
/**
 * @來源：Javascript中文網 - 前端進階資源教程 https://www.javascriptc.com/
 * @介紹：前端中文網是以前端進階資源教程分享為主的專業網站，包括：前端、大廠面試題、typescript教程、程序人生、React.js
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  if (nums.length < 3) return [];
  const list = [];
  nums.sort((a, b) => a - b);
  for (let i = 0; i < nums.length; i++) {
    //nums is sorted,so it's impossible to have a sum = 0
    if (nums[i] > 0) break;
    // skip duplicated result without set
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    let left = i + 1;
    let right = nums.length - 1;

    // for each index i
    // we want to find the triplet [i, left, right] which sum to 0
    while (left < right) {
      // since left < right, and left > i, no need to compare i === left and i === right.
      if (nums[left] + nums[right] + nums[i] === 0) {
        list.push([nums[left], nums[right], nums[i]]);
        // skip duplicated result without set
        while (nums[left] === nums[left + 1]) {
          left++;
        }
        left++;
        // skip duplicated result without set
        while (nums[right] === nums[right - 1]) {
          right--;
        }
        right--;
        continue;
      } else if (nums[left] + nums[right] + nums[i] > 0) {
        right--;
      } else {
        left++;
      }
    }
  }
  return list;
};
  var twoSum = function(nums, target) {
    for (let i = 0; i < nums.length - 1; i++) { // 每個人
      for (let j = i + 1; j < nums.length; j++) { // 都去問其他的人
        if (nums[i]+nums[j] === target) {
          return [nums[i], nums[j]]
        }
      }
    }
  }

// 作者：wonderful611
// 連結：https://leetcode-cn.com/problems/3sum/solution/three-sum-ti-jie-by-wonderful611/

Java 實現
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;
    }
}

//作者：guanpengchn
//連結：https://leetcode-cn.com/problems/3sum/solution/hua-jie-suan-fa-15-san-shu-zhi-he-by-guanpengchn/
C++ 實現
int len = nums.size();
for(int i=0; i<len-2; i++){
    for(int j=i+1; j<len-1;j++){
        for(int k=j+1; k<len; k++){
            if(nums[i] + nums[j] + nums[k] == 0){
                vector<int > vtemp{nums[i],nums[j],nums[k]};
                ret.push_back(vtemp);
            }
        }
    }
}

// 作者：edward_wang
// 連結：https://leetcode-cn.com/problems/3sum/solution/xiang-xi-jie-shi-shuang-zhi-zhen-jie-jue-san-shu-z/
Python 實現思路首先要熟悉求兩數之和的寫法，然後在 N > 2時，採用遞歸處理，一次減少1。這種寫法參考了國際站上的文章，我覺得是最好的一種解法了。
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if not nums: return []

        # 先排序，關鍵！
        nums.sort()
        ans = set()
        N, target = 3, 0
        self._find_sum(nums, 0, N, target, [], ans)
        return list(ans)

    def _find_sum(self, nums, start, N, target, path, ans):
        # terminator
        if len(nums) < N or N < 2: return
        # process
        if N == 2:
            # 兩數求和
            d = set()
            for j in range(start, len(nums)):
                if target - nums[j] in d:
                    ans.add(tuple(path + [target - nums[j], nums[j]]))
                else:
                    d.add(nums[j])
        else:
            for i in range(start, len(nums)):
                # 剪枝1: target比剩餘數字能組成的最小值還要小 或 比能組成的最大值還要大，就可以停止循環了
                if target < nums[i] * N or target > nums[-1] * N: break
                # 剪枝2: 去重
                if i > start and nums[i] == nums[i - 1]: continue
                # drill down
                self._find_sum(nums, i + 1, N - 1, target - nums[i], path + [nums[i]], ans)
        return

#作者：dz-lee
#連結：https://leetcode-cn.com/problems/3sum/solution/jian-ji-tong-yong-xie-fa-nshu-zhi-he-pythonxiang-x/
其他原題leetcode連結：15.3sum - https://leetcode-cn.com/problems/3sum/](https://leetcode-cn.com/problems/3sum/)合作方：JavaScript中文網 – 全球極客摯愛的技術成長平臺說明：leetcode 題解 | 每日一題🔥 所有題目並非全部為本人解答，部分為在複習學習中整理提取其他解題作者的優秀筆記，便於大家學習共同進步，如有侵權，請聯繫刪除。

相關焦點

  • leetcode-15三數之和
    三數之和：https://leetcode-cn.com/problems/3sum/1、題目描述
  • LeetCode-15.三數之和(3Sum)
    三數之和給你一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有滿足條件且不重複的三元組。注意：答案中不可以包含重複的三元組。
  • 四數之和(18)-四數之和(454)-LeetCode
    滿足要求的四元組集合為：[[-1,  0, 0, 1], [-2, -1, 1, 2], [-2,  0, 0, 2]]來源：LeetCode連結：https://leetcode-cn.com/problems/4sum（1）排序+雙指針    延續兩數之和、三數之和的雙指針+排序解題思路
  • LeetCode Weekly Contest 224 題解
    --InterviewProblem/blob/master/LeetCode/leetcode_number-of-rectangles-that-can-form-the-largest-square.cpp題解：模擬題。
  • 整數反轉 | Leetcode題解
    每次找到當前數的最後一位，然後作為反轉數字的第一位，例如123：123 --> 0*10  + 312  --> 3*10  + 21   --> 32*10 + 1再注意保存開始的正負狀態和結果的限制[−2^31, 2^31 − 1]。思路 2:本題如果不考慮溢出問題，是非常簡單的。
  • LeetCode Weekly Contest 204 題解
    /blob/master/LeetCode/leetcode_detect-pattern-of-length-m-repeated-k-or-more-times.cpp題解：模擬或者是單純的數組題。
  • LeetCode-18.四數之和(4Sum)
    四數之和給定一個包含 n 個整數的數組 nums 和一個目標值 target，判斷 nums 中是否存在四個元素 a，b，c 和 d ，使得 a + b + c + d 的值與 target 相等？找出所有滿足條件且不重複的四元組。注意：答案中不可以包含重複的四元組。
  • 【Leetcode刷題練Python】1. 兩數之和
    官方網址是：http://leetcode.com/，打開瀏覽器輸入網址，就可以在線寫代碼、提交、查看算法的優略以及個人別實現算法的對比等等。開箱即用，非常方便。上面收錄的算法題目，大多來自大公司的筆試面試題，分為簡單、中等、困難三個等級，從基礎到高級都有。
  • LeetCode 熱題 HOT 100 15. 三數之和
    題目給你一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？
  • LeetCode-1.兩數之和(Two Sum)
    相信每個想刷leetcode的人，第一次打開網站，就從這道題開始的。一起起航吧，Great Voyage.
  • 三數之和姊妹題——LeetCode題目16:最接近的三數之和
    找出 nums 中的三個整數，使得它們的和與 target 最接近。返回這三個數的和。假定每組輸入只存在唯一答案。示例輸入：nums=[-1, 2, 1, 4], target=1輸出：2解釋：與 target 最接近的三個數的和為 2. (-1 + 2 + 1 = 2).
  • ​LeetCode刷題實戰18: 四數之和
    今天和大家聊的問題叫做四數之和 ，我們先來看題面：https://leetcode-cn.com/problems/4sum/Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such
  • [LeetCode] 1022. Sum of Root To Leaf Binary Numbers 從根到葉的二進位數之和
    實際上就是一道變形的路徑之和的題目，關於路徑之和，LeetCode 有很多道題目，比如 Path Sum IV，Path Sum III，Binary Tree Maximum Path Sum，Path Sum II，Path Sum，和 Minimum Path Sum 等等。
  • 推薦4個基於 Java語言的開源 Leetcode 題解!算法面試不愁了!
    為了能夠幫助我們更好的刷 Leetcode，Guide 精選了一些不錯的基於 Java 題解的開源項目，文末有項目連結。下面的項目是根據下面三個標準選出：項目的質量如何，這一點可以從 star、issue 以及 pr 的數量側面反映出來。
  • 每天一道leetcode18-四數之和
    正當班主任要繼續發話，只聽到角落默默想起來一個聲音:」K2」前言 2018.11.20號打卡今天的題目leetcode61：https://leetcode-cn.com/problems/rotate-list/description/昨天的題解題目 每天一道leetcode18- 四數之和分類：雙指針
  • 三數之和 --- leetcode
    給你一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？
  • 每日一道 LeetCode (56):四數之和
    每日一道 LeetCode (56)：四數之和每天 3 分鐘，走上算法的逆襲之路。
  • ​LeetCode刷題實戰15題: 三數之和
    今天和大家聊的問題叫做三數之和 ，我們先來看題面：https://leetcode.com/problems/3sum/描述給定一個整數的數組，要求尋找當中所有的a，b，c三個數的組合，使得三個數的和為0.注意，即使數組當中的數有重複，同一個數也只能使用一次。
  • 兩數相加 | Leetcode題解
    如果，我們將這兩個數相加起來，則會返回一個新的鍊表來表示它們的和。您可以假設除了數字 0 之外，這兩個數都不會以 0 開頭。/problems/add-two-numbers/solution/liang-shu-xiang-jia-by-leetcode-solution/*/var addTwoNumbers = function(l1, l2) {    let head = null, tail = null;    let carry = 0;    while (l1
  • leetcode-cheatsheet 史詩級更新,來看看我是如何寫題解的
    ，插件現在內置題解模板功能，目前模板只有一套，這套模板是「我經常使用的題解模板」。最後祝大家寫出漂亮的題解！體驗優化「路由」記憶現在增加「路由」記憶功能。比如上面提到的「寫題解」功能，當你點擊寫題解按鈕後，會「自動定位到題解模板標籤頁」網站寬度調整之前考慮的僅僅是插件中使用，而現在除了在插件中運行，還可以在 PC 端運行。因此我增加了一個打包命令專門用來打包到 「PC 端」。