【附JS、Python、C++题解】Leetcode面试150题（9）——三数之和

一、题目​​​​​

15. 三数之和

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

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

二、思路

1. 我们要返回的是“所有和为0且不重复的三元组”，这是一个数组类型，数组里的每一个元素都是三元组；

2. 要有三个用于遍历的指针；

3. 判断条件就两个：

• i!=j、i!=k 且 j!= k 
• nums[i] + nums[j] + nums[k] == 0、

4. 如果直接遍历，重复次数太多了，如何解决？

【联想到“两数之和Ⅱ”的那道题，因为有了一个“非严格递增”的顺序条件，我们得以简化遍历的过程；在这里也可以借鉴这个思路——创造一个顺序出来】

该题题解见如下文章：
【附JS、Python、C++题解】Leetcode面试150题（7）-CSDN博客

三、代码

① JavaScript

function threeNums(nums){
    nums.sort((a,b)->a-b);
    let res = [];
    let l = nums.length;
    for(let i = 0; i<l-2; i++){
        if(i>0 && nums[i]===nums[i-1]){
            continue;
        }
        let j = i+1;
        let k = l-1;
        while(j<k){
            const sum = nums[i] + nums[j] + nums[k];
            if(sum === 0){
                res.push([nums[i], nums[j], nums[k]]);
                while(j<k && nums[j] === nums[j+1]){
                    j++;
                }
                while(j<k && nums[k] === nums[k-1]){
                    k--;
                }
                j++;
                i--;
            }else if(sum<0){
                j++;
            }
            else{
                K--;
            }
            
        }
    }
    return res;
}

② Python

def three_sum(nums):
    nums.sort()  # 先对数组进行排序
    res = []
    length = len(nums)

    for i in range(length - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        j, k = i + 1, length - 1

        while j < k:
            total = nums[i] + nums[j] + nums[k]
            if total == 0:
                res.append([nums[i], nums[j], nums[k]])
                # 避免重复计算
                while j < k and nums[j] == nums[j + 1]:
                    j += 1
                while j < k and nums[k] == nums[k - 1]:
                    k -= 1
                j += 1
                k -= 1
            elif total < 0:
                j += 1
            else:
                k -= 1

    return res

③ C++

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

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> res;
    int length = nums.size();

    // 先对数组进行排序
    sort(nums.begin(), nums.end());

    for (int i = 0; i < length - 2; ++i) {
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }

        int j = i + 1;
        int k = length - 1;

        while (j < k) {
            int total = nums[i] + nums[j] + nums[k];
            if (total == 0) {
                res.push_back({nums[i], nums[j], nums[k]});
                // 避免重复计算
                while (j < k && nums[j] == nums[j + 1]) {
                    ++j;
                }
                while (j < k && nums[k] == nums[k - 1]) {
                    --k;
                }
                ++j;
                --k;
            } else if (total < 0) {
                ++j;
            } else {
                --k;
            }
        }
    }

    return res;
}

四、反思

这道题自己做的时候并没有先进行排序，导致重复的次数很多。下次遇到遍历很复杂的问题，要先进行处理！！