一、题目
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
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;
}
四、反思
这道题自己做的时候并没有先进行排序,导致重复的次数很多。下次遇到遍历很复杂的问题,要先进行处理!!