小編給大家分享一下leetcode中如何解決三數(shù)之和問題，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！
目前創(chuàng)新互聯(lián)公司已為1000+的企業(yè)提供了網(wǎng)站建設、域名、網(wǎng)頁空間、網(wǎng)站改版維護、企業(yè)網(wǎng)站設計、云岡網(wǎng)站維護等服務，公司將堅持客戶導向、應用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。
https://leetcode-cn.com/problems/3sum/
給定一個包含 n 個整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？找出所有滿足條件且不重復的三元組。
注意：答案中不可以包含重復的三元組。
重慶分公司
重慶分公司
例如, 給定數(shù)組 nums = [-1, 0, 1, 2, -1, -4]，
滿足要求的三元組集合為：
[
[-1, 0, 1],
[-1, -1, 2]
]
標簽：數(shù)組遍歷
首先對數(shù)組進行排序，排序后固定一個數(shù)nums[i]，再使用左右指針指向nums[i]后面的兩端，數(shù)字分別為nums[L]和nums[R]，計算三個數(shù)的和sum判斷是否滿足為0，滿足則添加進結果集
如果nums[i]大于0，則三數(shù)之和必然無法等于0，結束循環(huán)
如果nums[i] == nums[i-1]，則說明該數(shù)字重復，會導致結果重復，所以應該跳過
當sum == 0時，nums[L] == nums[L+1]則會導致結果重復，應該跳過，L++
當sum == 0時，nums[R] == nums[R-1]則會導致結果重復，應該跳過，R--
時間復雜度：O(n^2)，n為數(shù)組長度
Java版本
class Solution {
public static List> threeSum(int[] nums) {
List> ans = new ArrayList();
Arrays.sort(nums); // 排序
int len = nums.length;
if(nums == null || len < 3) return ans;
for (int i = 0; i < len ; i++) {
if(nums[i] > 0) break; // 如果當前數(shù)字大于0，則三數(shù)之和一定大于0，所以結束循環(huán)
if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
int L = i+1;
int R = len-1;
while(L < R){
int sum = nums[i] + nums[L] + nums[R];
if(sum == 0){
ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
while (L
R--;
}
else if (sum < 0) L++;
else if (sum > 0) R--;
}
}
return ans;
}
}
JavaScript版本
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
let ans = [];
nums.sort((a, b) => a - b); // 排序
const len = nums.length;
if(nums == null || len < 3) return ans;
for (let i = 0; i < len ; i++) {
if(nums[i] > 0) break; // 如果當前數(shù)字大于0，則三數(shù)之和一定大于0，所以結束循環(huán)
if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
let L = i+1;
let R = len-1;
while(L < R){
const sum = nums[i] + nums[L] + nums[R];
if(sum == 0){
ans.push([nums[i],nums[L],nums[R]]);
while (L
R--;
}
else if (sum < 0) L++;
else if (sum > 0) R--;
}
}
return ans;
};
以上是“l(fā)eetcode中如何解決三數(shù)之和問題”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學習更多知識，歡迎關注創(chuàng)新互聯(lián)行業(yè)資訊頻道！
