Leetcode 15. 三数之和（画图分析）

力扣传送门(opens new window)

3Sum

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

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

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

解题思路：

当解题时，可以按照以下思路来理解和实现这段代码：

首先，对给定的整数数组 nums 进行排序
- 排序可以将数组中的元素按照从小到大的顺序排列，这样可以更方便地进行后续的处理和搜索。
- 排序后，可以使用双指针的方法来搜索满足条件的三元组。排序使得数组中的元素满足递增的顺序，可以通过移动指针来逼近满足条件的解，从而减少搜索的范围和复杂度。
- 排序后，可以通过判断当前元素的值来进行一些优化。比如，在遍历数组时，如果当前元素已经大于 0，那么由于数组已排序，后面的元素都大于 0，因此无论如何组合都不可能凑成满足条件的三元组，可以直接返回结果。
- 排序后，重复元素会相邻排列，这样可以方便地进行去重操作。通过比较当前元素与前一个元素是否相等，可以避免生成重复的三元组，从而减少最终结果中的重复项。
对于每一个元素 nums[i]，作为可能的三元组的第一个元素（a），尝试找到另外两个元素（b 和 c），使得 a + b + c = 0。
在遍历数组时，如果当前元素 nums[i] 大于 0，那么由于数组已排序，后面的元素都大于 0，因此无论如何组合都不可能凑成满足条件的三元组，直接返回结果。
在遍历数组时，如果当前元素 nums[i] 与前一个元素相同（即重复元素），则跳过该元素，以避免生成重复的三元组。（这里想一想为什么 nums[i]不和后一个元素比较呢？）
使用两个指针 left 和 right 分别指向当前元素的下一个元素和数组末尾元素。通过移动指针来搜索满足条件的 b 和 c。
当 nums[i] + nums[left] + nums[right] 大于 0 时，说明当前的 nums[right] 太大，需要将 right 指针左移，减小当前和。
当 nums[i] + nums[left] + nums[right] 小于 0 时，说明当前的 nums[left] 太小，需要将 left 指针右移，增大当前和。
当 nums[i] + nums[left] + nums[right] 等于 0 时，说明找到了满足条件的三元组。将该三元组添加到结果列表中，并进行去重操作。
- 去重逻辑包括：跳过重复的 b 元素，即当 nums[left] == nums[left + 1] 时，将 left 指针右移；
- 跳过重复的 c 元素，即当 nums[right] == nums[right - 1] 时，将 right 指针左移。
在循环结束后，返回结果列表，其中包含了所有满足条件的三元组。

三数之和1.jpg

三数之和2.jpg

下面是动态图演示

15.三数之和.gif

代码实现：

java

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> res = new ArrayList();
    if(nums == null || nums.length == 0){
        return res;
    }
  
    Arrays.sort(nums);
    // 如果第一个数字都大于0，则直接返回结果
    if(nums[0] > 0){
        return res;
    }

    for(int i = 0; i < nums.length; i++){
        int left = i + 1;
        int right = nums.length - 1;
        // 判断是否有重复元素
        if(i > 0 && nums[i] == nums[i - 1]){
            continue;
        }
        while(left < right){
            int sum = nums[i] + nums[left] + nums[right];
            if(sum > 0 ){
                // 和过大，减小右指针
                right--; 
            }else if(sum < 0){
                // 和过小，增大左指针
                left++; 
            }else{
                res.add(Arrays.asList(nums[i],nums[left],nums[right])); // 找到一组解
                while(left < right && nums[right] == nums[right - 1]){
                    // 跳过重复的右指针元素
                    right--; 
                }
                while(left < right && nums[left] == nums[left + 1]){
                    // 跳过重复的左指针元素
                    left++; 
                }
                right--;
                left++;
            }
        }
    }
    return res;
}

python3

from typing import List

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        if not nums or len(nums) == 0:
            return res
         # 对数组进行排序
        nums.sort() 
        if nums[0] > 0:
         # 如果最小数大于 0，直接返回
            return res  
  
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i - 1]:
                 # 跳过重复的元素
                continue 
             # 定义双指针
            left, right = i + 1, len(nums) - 1 
            while left < right:
                # 计算三数之和
                sum = nums[i] + nums[left] + nums[right]  
                if sum > 0:
                     # 如果和大于 0，移动右指针
                    right -= 1 
                elif sum < 0:
                     # 如果和小于 0，移动左指针
                    left += 1 
                else:
                    # 找到一组解
                    res.append([nums[i], 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 res

c++

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        if (nums.empty()) {
            return res;
        }
        // 对数组进行排序
        sort(nums.begin(), nums.end()); 
        if (nums[0] > 0) {
            // 如果最小数大于 0，直接返回
            return res; 
        }

        for (int i = 0; i < nums.size(); ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                // 跳过重复的元素
                continue; 
            }
            // 定义双指针
            int left = i + 1, right = nums.size() - 1; 
            while (left < right) {
                // 计算三数之和
                int sum = nums[i] + nums[left] + nums[right]; 
                if (sum > 0) {
                    // 如果和大于 0，移动右指针
                    right--; 
                } else if (sum < 0) {
                    // 如果和小于 0，移动左指针
                    left++; 
                } else {
                    // 找到一组解
                    res.push_back({nums[i], nums[left], nums[right]}); 
                    // 跳过重复的左指针
                    while (left < right && nums[left] == nums[left + 1]) left++; 
                    // 跳过重复的右指针
                    while (left < right && nums[right] == nums[right - 1]) right--; 
                    left++;
                    right--;
                }
            }
        }
        return res;
    }
};

时间复杂度

排序的时间复杂度：
- 对 nums 进行排序需要 O(N log N) 的时间。
双指针查找部分：
- 在排序后的数组中，外层循环从 0 到 N-1，时间复杂度是 O(N)。
- 对于每一个 i，双指针的部分需要 O(N) 的时间（左指针和右指针每次移动一次，共需最多 N 次移动）。
- 因此，整体双指针部分的时间复杂度是 O(N²)。

综合来看，这道题的时间复杂度为 O(N²)。排序的 O(N log N) 相对较小，因此整体主导时间复杂度是 O(N²)。

空间复杂度

输入数组存储：输入数组 nums 占用 O(N) 的空间。
返回结果的存储：结果集 res 是存储三元组的二维数组，最坏情况下，空间复杂度可以达到 O(K)，其中 K 是返回的三元组的个数。
排序过程的辅助空间：如果使用原地排序，空间复杂度为 O(1)；如果使用其他非原地排序算法，可能需要 O(N) 的辅助空间。

总空间复杂度：最坏情况下为 O(N + K)，其中 N 是输入数组的长度，K 是结果集中三元组的个数。

目录CONTENT

Leetcode 15. 三数之和（画图分析）

Leetcode 15. 三数之和（画图分析）

解题思路：

代码实现：

时间复杂度

空间复杂度

评论区