Matarialize中文社区-三数之和

三数之和

不秃顶程序猿 2024-08-07 13:06:48

779 数组,双指针,排序专栏

给你一个整数数组 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
-105 <= nums[i] <= 105

解法一：

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
    if (!nums || nums.length < 3) {
        return [];
    }
    let sums = [];
    let sumsMap = [];
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            for (let k = j + 1; k < nums.length; k++) {
                if ((nums[i] + nums[j] + nums[k]) === 0) {
                    let tmp = [
                        nums[i],
                        nums[j],
                        nums[k]
                    ];
                    const tmpStr = tmp.sort((a, b) => { return a - b; }).join('');
                    if (sumsMap.indexOf(tmpStr) !== -1) {
                        continue;
                    }
                    sumsMap.push(tmpStr);
                    sums.push(tmp);
                }
            }
        }
    }
    return sums;
};

解法二：

要解决这个问题，我们需要找到一个整数数组 nums 中的所有不重复的三元组 [nums[i], nums[j], nums[k]]，使得它们的和为零。经典的方法是使用排序加上双指针来实现。下面是详细的解决方案及其实现。

算法步骤

排序数组：

首先对数组进行排序，这有助于使用双指针方法有效地找到合适的三元组。

遍历数组：

对于每个元素 nums[i]，在剩下的元素中使用双指针寻找另外两个元素 nums[j] 和 nums[k]，使得 nums[i] + nums[j] + nums[k] == 0。

双指针查找：

如果和为 0，则找到一个三元组，存储结果，并移动两个指针以寻找其他可能的组合。
如果和小于 0，说明需要更大的数，因此移动 left 指针以增加和。
如果和大于 0，说明需要更小的数，因此移动 right 指针以减小和。

使用两个指针 left 和 right，分别指向 i+1 和数组的末尾。
根据 nums[i] + nums[left] + nums[right] 的和与 0 的关系调整指针：

跳过重复元素：

为了避免重复的三元组结果，需要跳过数组中相邻的相同元素。即，当 nums[i] == nums[i-1] 时，跳过该元素以避免重复计算。

结果去重：

使用内置的数据结构来避免三元组重复，可以通过哈希集合或者简单地在算法中处理。

代码实现

def threeSum(nums):
    # 对数组进行排序
    nums.sort()
    result = []
    n = len(nums)
    # 遍历数组，寻找三元组
    for i in range(n - 2):        # 如果当前数字与上一个数字相同，跳过以避免重复结果
        if i > 0 and nums[i] == nums[i - 1]:            continue

        # 双指针初始化
        left, right = i + 1, n - 1

        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 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

            elif total < 0:                # 总和小于0，移动左指针
                left += 1
            else:                # 总和大于0，移动右指针
                right -= 1

    return result

# 示例测试nums = [-1, 0, 1, 2, -1, -4]
print(threeSum(nums))
# 输出: [[-1, -1, 2], [-1, 0, 1]]

复杂度分析

时间复杂度：O(n²)，其中 n 是数组的长度。排序的时间复杂度是 O(n log n)，而双指针查找的时间复杂度是 O(n²)。
空间复杂度：O(1)（不考虑存储结果的空间），因为我们只使用了常量级别的额外空间来处理指针。

说明

去重处理：通过跳过相同的元素，避免了重复的三元组。在 nums[i] 的选择和 left、right 指针的移动中都进行了去重处理。
边界条件：遍历数组时只到 n - 2，因为至少需要三个数来形成一个三元组。
双指针策略：利用双指针从两端收缩，可以高效地找到满足条件的组合，避免了不必要的计算。

这种方法利用了排序和双指针的优势，使得我们能够在合理的时间复杂度下解决该问题。

评论区

字数统计

评论列表

不秃顶程序猿

JavaScript语言

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    if (!nums || nums.length < 3) {
        return [];
    }
    nums.sort((a,b) => {return a - b;});
    let sums = [];
    for (let i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        let left = i + 1;
        let right = nums.length - 1;
        while (left < right) {
            let total = nums[i] + nums[left] + nums[right];
            if (total === 0) {
                sums.push([nums[i], nums[left], nums[right]]);
                while (left < right && nums[left] == nums[left + 1]) {
                    left += 1;
                }

                while (left < right && nums[right] == nums[right - 1]) {
                    right -= 1;
                }
                left += 1;
                right -= 1;
            } else if (total < 0) {
                left += 1;
            } else {
                right -= 1;
            }
        }
    }
    return sums;
}

作者信息

不秃顶程序猿

做最厉害的不秃顶程序猿

私信专栏

热门专栏

移动零

LeetCode 热题 100 - 两数之和

盛最多水的容器

三数之和

最长连续序列

在网页中使用 Materialize 实现中文日期选择器

MaterializeCSS轮播组件：构建动态网页内容的利器

在网页中使用 Materialize 实现日期选择器

使用 Materialize 实现图文列表布局

微信小程序开发：实现授权登录，获取用户手机号及用户信息