15.三数之和

标签: array, two-pointers, sort

难度: Medium

通过率: 35.92%

原题链接: https://leetcode.com/problems/3sum/description/

题目描述

给定一个整数数组 nums，返回所有和为0且不重复的三元组 [nums[i], nums[j], nums[k]]，其中 i != j，i != k，j != k。注意：解集不能包含重复的三元组。

解题思路

解题思路可以使用排序加双指针的方法：

1. 首先对数组进行排序。
2. 在排序后的数组中，固定第一个数字，使用双指针从其后部分寻找满足条件的其他两个数。
3. 对于第一个数，遍历至数组倒数第三个位置，因为我们需要至少三个数。
4. 如果第一个数与其前一个数相同（这种情况可能在重复解集中存在），则跳过该数。
5. 设定两个指针：第二个数指针 left 指向当前位置的下一个位置，第三个数指针 right 指向数组的末尾。
6. 计算当前三数之和：如果和为零，将三元组加入结果集中，并移动 left 和 right 指针。如果有重复的 left 或 right 元素，跳过重复的元素。
7. 如果和小于零，则增加 left 指针以使总和变大。如果和大于零，则减少 right 指针以使总和变小。
8. 重复步骤5-7直到 left 和 right 相遇。

这样就能在 $\mathcal{O}(n^2)$ 的时间复杂度内找到所有没有重复的三元组合。

代码实现

Python

def threeSum(nums):
    # 首先对数组进行排序
    nums.sort()
    result = []
    # 遍历每个数字作为第一个数
    for i in range(len(nums) - 2):
        # 如果这个数和之前的数相同，则跳过，以避免重复的解
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        # 初始化两个指针
        left, right = i + 1, len(nums) - 1
        # 双指针方法找另外两个数
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total < 0:
                # 总和小于0，增加左指针
                left += 1
            elif total > 0:
                # 总和大于0，减少右指针
                right -= 1
            else:
                # 总和为0
                result.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 result

C++

std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
    // 首先对数组进行排序
    std::sort(nums.begin(), nums.end());
    std::vector<std::vector<int>> result;
    // 遍历每个数字作为第一个数
    for (int i = 0; i < nums.size() - 2; ++i) {
        // 如果这个数和之前的数相同，则跳过，以避免重复的解
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        // 初始化两个指针
        int left = i + 1, right = nums.size() - 1;
        // 双指针方法找另外两个数
        while (left < right) {
            int total = nums[i] + nums[left] + nums[right];
            if (total < 0) {
                // 总和小于0，增加左指针
                ++left;
            } else if (total > 0) {
                // 总和大于0，减少右指针
                --right;
            } else {
                // 总和为0
                result.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 result;
}

JavaScript

function threeSum(nums) {
    // 首先对数组进行排序
    nums.sort((a, b) => a - b);
    const result = [];
    // 遍历每个数字作为第一个数
    for (let i = 0; i < nums.length - 2; i++) {
        // 如果这个数和之前的数相同，则跳过，以避免重复的解
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        // 初始化两个指针
        let left = i + 1, right = nums.length - 1;
        // 双指针方法找另外两个数
        while (left < right) {
            const total = nums[i] + nums[left] + nums[right];
            if (total < 0) {
                // 总和小于0，增加左指针
                left++;
            } else if (total > 0) {
                // 总和大于0，减少右指针
                right--;
            } else {
                // 总和为0
                result.push([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 result;
}

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 首先对数组进行排序
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        // 遍历每个数字作为第一个数
        for (int i = 0; i < nums.length - 2; i++) {
            // 如果这个数和之前的数相同，则跳过，以避免重复的解
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            // 初始化两个指针
            int left = i + 1, right = nums.length - 1;
            // 双指针方法找另外两个数
            while (left < right) {
                int total = nums[i] + nums[left] + nums[right];
                if (total < 0) {
                    // 总和小于0，增加左指针
                    left++;
                } else if (total > 0) {
                    // 总和大于0，减少右指针
                    right--;
                } else {
                    // 总和为0
                    result.add(Arrays.asList(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 result;
    }
}

复杂度分析

时间复杂度：排序需要 $\mathcal{O}(n \log n)$ 时间，找到所有三元组的时间复杂度为 $\mathcal{O}(n^2)$，因此总的时间复杂度为 $\mathcal{O}(n^2)$。 空间复杂度：由于需要输出保存结果的数组，最坏情况下需要 $\mathcal{O}(n^2)$ 的空间用于存储所有可能的结果集。除了用于存储输出的空间外，只需要常数的额外空间。