【附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]:continuej, k = i + 1, length - 1while 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 += 1while j < k and nums[k] == nums[k - 1]:k -= 1j += 1k -= 1elif total < 0:j += 1else:k -= 1return 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;
}

四、反思

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