Skip to content

15-3sum.md

Latest commit

 

History

History
543 lines (422 loc) · 15.2 KB

15-3sum.md

File metadata and controls

543 lines (422 loc) · 15.2 KB
Raw

15. 三数之和 - LeetCode Python/Java/C++/JS/C#/Go/Ruby 题解

🚀 打造你的开发者个人IP

掌握算法是成功的基石，而全方位展示你的才华则是获得垂青的关键。

我们向你推荐 Like.dev —— 专为程序员打造的“全能型”个人品牌展示平台。

三位一体（All-In-One）的职场利器：

  • 📄 简历 + 作品集 + 博客： 将你的 GitHub 项目、技术心得与职场经历完美融合。
  • 🌐 永久免费自定义域名： 支持绑定你自己的独立域名，且该功能永久免费。
  • ✨ 顶级行业子域名： 提供 name.cto.page、name.engineer.dev 等极具职业含金量的专属域名。
  • 🔗 超酷超短个人主页： 获得极其简练的社交名片，如 is.bio/yourname 或 an.dev/yourname。

立即前往 Like.dev 打造你的个人品牌 →

访问原文链接：15. 三数之和 - LeetCode Python/Java/C++/JS/C#/Go/Ruby 题解，体验更佳！

力扣链接：15. 三数之和, 难度等级：中等。

LeetCode “15. 三数之和”问题描述

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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

[示例 1]

输入: nums = [-1,0,1,2,-1,-4]

输出: [[-1,-1,2],[-1,0,1]]

解释:

nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

[示例 2]

输入: nums = [0,1,1]

输出: []

解释: 唯一可能的三元组和不为 0 。

[示例 3]

输入: nums = [0,0,0]

输出: [[0,0,0]]

解释: 唯一可能的三元组和为 0 。

[约束]

  • 3 <= nums.length <= 3000
  • -10^5 <= nums[i] <= 10^5

[Hints]

提示 1 So, we essentially need to find three numbers `x`, `y`, and `z` such that they add up to the given value. If we fix one of the numbers say `x`, we are left with the two-sum problem at hand!
提示 2 For the two-sum problem, if we fix one of the numbers, say `x`, we have to scan the entire array to find the next number `y`, which is `value - x` where value is the input parameter. Can we change our array somehow so that this search becomes faster?
提示 3 The second train of thought for two-sum is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?

思路 1

  1. 三个数相加等于0，等同于两个数相加的和等于负的第三个数。
  2. 有两种方案可供选择：
    1. 先定下一个数，然后查找另外两个数。
    2. 先定下两个数，然后查找第三个数。
  3. 如果选择方案2，需要用到Map。因为需要对nums去重复；在Map中查找第三个数时，还需要避开已经定下的两个数，实现起来会比较麻烦。
  4. 如果选择方案1，查找另外两个数时，需要用到双指针算法。
  5. 对于方案2，仅给出了Python示例代码。下文重点讲方案1。

步骤

  1. 对nums进行排序。

  2. 遍历nums。

  3. 伪代码：

    for (i = 0; i < nums.length; i++) {
   left = i + 1
   right = nums.length - 1

   while (left < right) {
      if (condition1) {
         left += 1
      } else (condition2) {
         right -= 1
      }
   }
}

复杂度

  • 时间复杂度: O(N * N).
  • 空间复杂度: O(N).

Python

# If you want the program to run faster, uncomment the two places in the code. 
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        # nums_2 = []
        # for i, num in enumerate(nums):
        #     if i >= 3 and num == nums[i - 1] == nums[i - 2] == nums[i - 3]:
        #         continue
        #     nums_2.append(num)
        # nums = nums_2
        results = set()

        for i, num in enumerate(nums[:len(nums) - 2]):
            # if num > 0:
            #     break
            left = i + 1
            right = len(nums) - 1

            while left < right:
                sum_ = nums[left] + nums[right]
                if sum_ == -num:
                    results.add((num, nums[left], nums[right]))
                    left += 1
                elif sum_ > -num:
                    right -= 1
                else:
                    left += 1
        
        return list(results)

Ruby

# @param {Integer[]} nums
# @return {Integer[][]}
def three_sum(nums)
  nums.sort!
  results = Set.new

  nums_2 = []
  nums.each_with_index do |num, i|
    next if i >= 3 && num == nums[i - 1] && num == nums[i - 2] && num == nums[i - 3]
    nums_2.append(num)
  end

  nums = nums_2

  # Iterate through each number as potential first element
  (0...nums.length - 2).each do |i|
    break if nums[i] > 0

    left = i + 1
    right = nums.length - 1

    # Two-pointer approach for remaining elements
    while left < right
      current_sum = nums[i] + nums[left] + nums[right]
      if current_sum == 0
        # Add sorted triplet to avoid duplicates
        results.add([nums[i], nums[left], nums[right]])
        left += 1
        right -= 1
      elsif current_sum < 0
        left += 1 # Need larger sum
      else
        right -= 1 # Need smaller sum
      end
    end
  end

  results.to_a
end

Go

func threeSum(nums []int) [][]int {
    sort.Ints(nums)

    nums2 := make([]int, 0)
    for i, num := range nums {
        if i >= 3 && num == nums[i-1] && nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3] {
            continue
        }
        nums2 = append(nums2, num)
    }

    nums = nums2
    results := make([][]int, 0)
    seen := make(map[string]bool)

    for i := 0; i < len(nums)-2; i++ {
        // if nums[i] > 0 {
        //     break
        // }

        left := i + 1
        right := len(nums) - 1

        for left < right {
            sum := nums[left] + nums[right]
            if sum == -nums[i] {
                triplet := []int{nums[i], nums[left], nums[right]}
                key := fmt.Sprintf("%d,%d,%d", triplet[0], triplet[1], triplet[2])
                if !seen[key] {
                    results = append(results, triplet)
                    seen[key] = true
                }
                left++
            } else if sum > -nums[i] {
                right--
            } else {
                left++
            }
        }
    }

    return results
}

C++

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        // Uncomment to speed up
        // vector<int> nums2;
        // for (int i = 0; i < nums.size(); i++) {
        //     if (i >= 3 && nums[i] == nums[i-1] && nums[i-1] == nums[i-2] &&
        //     nums[i-2] == nums[i-3]) {
        //         continue;
        //     }
        //     nums2.push_back(nums[i]);
        // }
        // nums = nums2;

        vector<vector<int>> results;
        set<vector<int>> seen;

        for (int i = 0; i < nums.size() - 2; i++) {
            // Uncomment to speed up
            // if (nums[i] > 0) {
            //     break;
            // }
            int left = i + 1;
            int right = nums.size() - 1;

            while (left < right) {
                int sum = nums[left] + nums[right];

                if (sum == -nums[i]) {
                    vector<int> triplet = {nums[i], nums[left], nums[right]};

                    if (seen.find(triplet) == seen.end()) {
                        results.push_back(triplet);
                        seen.insert(triplet);
                    }

                    left++;
                } else if (sum > -nums[i]) {
                    right--;
                } else {
                    left++;
                }
            }
        }

        return results;
    }
};

JavaScript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    nums.sort((a, b) => a - b);

    // Uncomment to speed up
    // let nums2 = [];
    // for (let i = 0; i < nums.length; i++) {
    //     if (i >= 3 && nums[i] === nums[i-1] && nums[i-1] === nums[i-2] && nums[i-2] === nums[i-3]) {
    //         continue;
    //     }
    //     nums2.push(nums[i]);
    // }
    // nums = nums2;
    
    const results = [];
    const seen = new Set();
    
    for (let i = 0; i < nums.length - 2; i++) {
        // Uncomment to speed up
        // if (nums[i] > 0) {
        //     break;
        // }
        let left = i + 1;
        let right = nums.length - 1;
        
        while (left < right) {
            const sum = nums[left] + nums[right];

            if (sum === -nums[i]) {
                const triplet = [nums[i], nums[left], nums[right]];
                const key = triplet.join(',');
                if (!seen.has(key)) {
                    results.push(triplet);
                    seen.add(key);
                }
                left++;
            } else if (sum > -nums[i]) {
                right--;
            } else {
                left++;
            }
        }
    }
    
    return results;
};

C#

public class Solution {
    public IList<IList<int>> ThreeSum(int[] nums) {
        Array.Sort(nums);

        // Uncomment to speed up
        // var nums2 = new List<int>();
        // for (int i = 0; i < nums.Length; i++) {
        //     if (i >= 3 && nums[i] == nums[i-1] && nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3]) {
        //         continue;
        //     }
        //     nums2.Add(nums[i]);
        // }
        // nums = nums2.ToArray();
        
        var results = new List<IList<int>>();
        var seen = new HashSet<string>();
        
        for (int i = 0; i < nums.Length - 2; i++) {
            // Uncomment to speed up
            // if (nums[i] > 0) {
            //     break;
            // }
            int left = i + 1;
            int right = nums.Length - 1;
            
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum == -nums[i]) {
                    var triplet = new List<int> { nums[i], nums[left], nums[right] };
                    string key = string.Join(",", triplet);
                    if (!seen.Contains(key)) {
                        results.Add(triplet);
                        seen.Add(key);
                    }
                    left++;
                } else if (sum > -nums[i]) {
                    right--;
                } else {
                    left++;
                }
            }
        }
        
        return results;
    }
}

Java

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);

        // Uncomment to speed up
        // List<Integer> nums2 = new ArrayList<>();
        // for (int i = 0; i < nums.length; i++) {
        //     if (i >= 3 && nums[i] == nums[i-1] && nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3]) {
        //         continue;
        //     }
        //     nums2.add(nums[i]);
        // }
        // nums = nums2.stream().mapToInt(i -> i).toArray();
        
        List<List<Integer>> results = new ArrayList<>();
        var seen = new HashSet<>();
        
        for (int i = 0; i < nums.length - 2; i++) {
            // Uncomment to speed up
            // if (nums[i] > 0) {
            //     break;
            // }
            int left = i + 1;
            int right = nums.length - 1;
            
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum == -nums[i]) {
                    List<Integer> triplet = Arrays.asList(nums[i], nums[left], nums[right]);
                    if (!seen.contains(triplet)) {
                        results.add(triplet);
                        seen.add(triplet);
                    }
                    left++;
                } else if (sum > -nums[i]) {
                    right--;
                } else {
                    left++;
                }
            }
        }
        
        return results;
    }
}

Other languages

// Welcome to create a PR to complete the code of this language, thanks!

思路 2

请参考题解1的思路，本处仅给出代码，用来解释为什么使用 Map 不是一个好办法。

复杂度

  • 时间复杂度: O(N * N).
  • 空间复杂度: O(N).

Python

# from collections import defaultdict

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums = duplicate_removed_nums(nums)

        results = set()
        num_to_indices = defaultdict(list)

        for i, num in enumerate(nums):
            num_to_indices[num].append(i)

        for i in range(len(nums) - 1):
            for j in range(i + 1, len(nums)):
                if -(nums[i] + nums[j]) in num_to_indices:
                    for index in num_to_indices[-(nums[i] + nums[j])]:
                        if index not in (i, j):
                            result = [nums[i], nums[j], nums[index]]
                            result.sort()
                            results.add(tuple(result))

        return list(results)


def duplicate_removed_nums(nums):
    num_to_count = defaultdict(int)

    for i, num in enumerate(nums):
        if num_to_count[num] <= 2 or (num_to_count[num] <= 3 and num == 0):
            num_to_count[num] += 1

    new_nums = []

    for num in num_to_count:
        new_nums.extend([num] * num_to_count[num])
    
    return new_nums

Other languages

// Welcome to create a PR to complete the code of this language, thanks!

🚀 打造你的开发者个人IP

掌握算法是成功的基石，而全方位展示你的才华则是获得垂青的关键。

我们向你推荐 Like.dev —— 专为程序员打造的“全能型”个人品牌展示平台。

三位一体（All-In-One）的职场利器：

  • 📄 简历 + 作品集 + 博客： 将你的 GitHub 项目、技术心得与职场经历完美融合。
  • 🌐 永久免费自定义域名： 支持绑定你自己的独立域名，且该功能永久免费。
  • ✨ 顶级行业子域名： 提供 name.cto.page、name.engineer.dev 等极具职业含金量的专属域名。
  • 🔗 超酷超短个人主页： 获得极其简练的社交名片，如 is.bio/yourname 或 an.dev/yourname。

立即前往 Like.dev 打造你的个人品牌 →

访问原文链接：15. 三数之和 - LeetCode Python/Java/C++/JS/C#/Go/Ruby 题解，体验更佳！

GitHub 仓库: leetcode-python-java.