LeetCode 热题100 15. 三数之和

LeetCode 热题100 | 15. 三数之和

大家好，今天我们来解决一道经典的算法题——三数之和。这道题在 LeetCode 上被标记为中等难度，要求我们从一个整数数组中找到所有不重复的三元组，使得三元组的和为 0。下面我将详细讲解解题思路，并附上 Python 代码实现。

题目描述

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

示例：

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

解题思路

这道题的核心是找到所有满足条件的三元组，同时避免重复。我们可以通过排序数组和双指针法来高效地解决这个问题。

核心思想

1. 排序数组：

   • 将数组排序，方便后续使用双指针法。

2. 遍历数组：

   • 固定一个数 nums[i]，然后在剩下的数组中使用双指针法寻找两个数 nums[left] 和 nums[right]，使得 nums[i] + nums[left] + nums[right] == 0。

3. 双指针法：

   • 初始化 left = i + 1，right = len(nums) - 1。
   • 如果 nums[i] + nums[left] + nums[right] < 0，则 left 右移。
   • 如果 nums[i] + nums[left] + nums[right] > 0，则 right 左移。
   • 如果 nums[i] + nums[left] + nums[right] == 0，则找到一个三元组，记录下来，并跳过重复的元素。

4. 去重：

   • 在遍历过程中，跳过重复的 nums[i]、nums[left] 和 nums[right]，避免重复的三元组。

代码实现

def threeSum(nums):
    """
    :type nums: List[int]
    :rtype: List[List[int]]
    """
    nums.sort()  # 排序数组
    result = []  # 存储结果
    
    for i in range(len(nums) - 2):  # 遍历数组，固定 nums[i]
        if i > 0 and nums[i] == nums[i - 1]:  # 跳过重复的 nums[i]
            continue
        
        left, right = i + 1, len(nums) - 1  # 初始化双指针
        while left < right:
            total = nums[i] + nums[left] + nums[right]  # 计算三数之和
            if total < 0:
                left += 1  # 和小于 0，左指针右移
            elif total > 0:
                right -= 1  # 和大于 0，右指针左移
            else:
                result.append([nums[i], nums[left], nums[right]])  # 找到一个三元组
                # 跳过重复的 nums[left] 和 nums[right]
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
    
    return result

代码解析

1. 排序数组：

   • 将数组排序，方便后续使用双指针法。

2. 遍历数组：

   • 固定一个数 nums[i]，然后在剩下的数组中使用双指针法寻找两个数 nums[left] 和 nums[right]。

3. 双指针法：

   • 初始化 left = i + 1，right = len(nums) - 1。
   • 根据三数之和的大小，移动 left 或 right 指针。

4. 去重：

   • 在遍历过程中，跳过重复的 nums[i]、nums[left] 和 nums[right]，避免重复的三元组。

复杂度分析

• 时间复杂度：O(n²)，其中 n 是数组的长度。排序的时间复杂度为 O(n log n)，双指针法的时间复杂度为 O(n²)。
• 空间复杂度：O(1)，只使用了常数个额外空间。

示例运行

示例 1

# 输入：nums = [-1,0,1,2,-1,-4]
nums = [-1, 0, 1, 2, -1, -4]
print(threeSum(nums))  # 输出: [[-1, -1, 2], [-1, 0, 1]]

示例 2

# 输入：nums = [0,1,1]
nums = [0, 1, 1]
print(threeSum(nums))  # 输出: []

示例 3

# 输入：nums = [0,0,0]
nums = [0, 0, 0]
print(threeSum(nums))  # 输出: [[0, 0, 0]]

总结

通过排序数组和双指针法，我们可以高效地找到所有满足条件的三元组，并避免重复。这种方法的时间复杂度为 O(n²)，能够处理较大的输入规模。希望这篇题解对你有帮助！如果还有其他问题，欢迎继续提问！

关注我，获取更多算法题解和编程技巧！