015. 3Sum
难度: Medium
刷题内容
原题连接
- https://leetcode.com/problems/3sum
内容描述
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
解题方案
思路 **- 时间复杂度: O(N²)*- 空间复杂度: O(N)***
代码：
/**
* @param {number[]} nums
* @return {number[][]}
*/
let threeSum = function(nums, n = 0) {
let result = [];
let len = nums.length;
if(!len) return result;
// 对数组进行排序
nums.sort((a,b)=>a-b);
for(let k = 0; k<len; k++){
//重复的元素则结果也一样，所以跳过该循环
if(k>0 && nums[k-1] === nums[k]){
continue;
}
let target = n - nums[k];
let i = k + 1;
let j = len -1;
while(i<j){
if(nums[i] + nums[j] === target){
result.push([nums[k],nums[i],nums[j]]);
while (i<j && nums[i] === nums[i+1]) i++;
while (i<j && nums[j] === nums[j-1]) j--;
i++;
j--;
}else if(nums[i] + nums[j] > target){
j--;
}else{
i++
}
}
}
return result;
};
