15. 三数之和
学习链接
个人思路
这道题用纯哈希法很难，因为需要考察三个不重复的数，要各种剪枝。这道题适合双指针的方法。
大概思路：
先排序，做一个for循环，设置
left = i + 1、 right = 数组结尾 双指针，if ((i + left + right) > target){ right -- } else { left ++ }
解题代码
注意三个去重
/** * @param {number[]} nums * @return {number[][]} */ var threeSum = function(nums) { let res = [] nums.sort((a,b)=>a-b) for(let i = 0; i < nums.length - 2; i++){ if (nums[i] === nums[i - 1]) { // i 去重 continue; } let left = i + 1 let right = nums.length - 1 while(right > left){ let threeSum = nums[i] + nums[left] + nums[right] if(threeSum > 0){ right -- } else if(threeSum < 0){ left ++ } else{ res.push([nums[i],nums[left],nums[right]]) while(left < right && nums[left] === nums[left + 1]){ // left去重 left ++ } while(left < right && nums[right] === nums[right - 1]){ // right去重 right -- } left ++ right -- } } } return res };
18. 四数之和
学习链接
个人思路
和3num一样，多一层for循环
解题代码
/** * @param {number[]} nums * @param {number} target * @return {number[][]} */ var fourSum = function(nums, target) { let res = [] nums.sort((a,b)=>a-b) for(let i = 0; i < nums.length - 2; i++){ if (nums[i] === nums[i - 1]) { // i 去重 continue; } for(let j = i + 1;j<nums.length - 2;j++){ let left = j + 1 let right = nums.length - 1 if(j > i + 1 && nums[j] === nums[j - 1]) { // j去重 这块一开始没想清楚 continue; } while(right > left){ let four = nums[i] + nums[left] + nums[right] + nums[j] if(four > target){ right -- } else if(four < target){ left ++ } else{ res.push([nums[i], nums[j],nums[left],nums[right]]) while(left < right && nums[left] === nums[left + 1]){ // left去重 left ++ } while(left < right && nums[right] === nums[right - 1]){ // right去重 right -- } left ++ right -- } } } } return res };