給你一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums登澜，判斷 nums 中是否存在三個(gè)元素 a，b，c 扰路，使得 a + b + c = 0 尤溜？請你找出所有滿足條件且不重復(fù)的三元組。
注意：答案中不可以包含重復(fù)的三元組汗唱。
示例：
給定數(shù)組 nums = [-1, 0, 1, 2, -1, -4]宫莱，
滿足要求的三元組集合為：
[
[-1, 0, 1],
[-1, -1, 2]
]
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/3sum
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)哩罪，非商業(yè)轉(zhuǎn)載請注明出處授霸。
先排好序，利用有序數(shù)組 雙指針的方式實(shí)現(xiàn)
public List<List<Integer>> threeSum(int[] nums) {
//用鏈表防止發(fā)生擴(kuò)容
List<List<Integer>> list = new LinkedList<>();
if (nums.length < 3) {
return list;
}
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
//為了保證不加入重復(fù)的 list,因?yàn)槭怯行虻募什澹匀绻颓耙粋€(gè)元素相同碘耳，只需要繼續(xù)后移就可以
// nums[i] == nums[i - 1] 則 i++
if ((i > 0 && nums[i] == nums[i - 1])) {
continue;
}
int left = i + 1;
int right = nums.length - 1;
int val = 0 - nums[i];
while (left < right) {
if (nums[left] + nums[right] == val) {
List<Integer> subList = Arrays.asList(nums[i], nums[left], nums[right]);
list.add(subList);
//元素相同要后移
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
//元素相同要前移
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
}
//如果相加比 val 小 則 left 后移
if (nums[left] + nums[right] < val) {
left++;
} else { //如果相加比 val 大 則 right 前移
right--;
}
}
}
return list;
}
時(shí)間復(fù)雜度：O（n2），n 指的是 num
空間復(fù)雜度：O（N）框弛，最壞情況
[16. 最接近的三數(shù)之和]
給定一個(gè)包括 n 個(gè)整數(shù)的數(shù)組 nums 和 一個(gè)目標(biāo)值 target辛辨。找出 nums 中的三個(gè)整數(shù)，使得它們的和與 target 最接近瑟枫。返回這三個(gè)數(shù)的和斗搞。假定每組輸入只存在唯一答案。
示例：
輸入：nums = [-1,2,1,-4], target = 1
輸出：2
解釋：與 target 最接近的和是 2 (-1 + 2 + 1 = 2) 慷妙。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/3sum-closest
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有僻焚。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處膝擂。
public int threeSumClosest(int[] nums, int target) {
//先排序
Arrays.sort(nums);
int ret = 0;
int min = Integer.MAX_VALUE;
for (int i = 0; i < nums.length - 2; i++) {
if(i>0&&nums[i]==nums[i-1]){
continue;
}
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (Math.abs(sum - target) < min) {
min = Math.abs(nums[i] + nums[left] + nums[right] - target);
ret = nums[i] + nums[left] + nums[right];
}
if (sum > target) {
while (left<right&&nums[right]==nums[right-1]){
right--;
}
right--;
} else {
while (left<right&&nums[left]==nums[left+1]){
left++;
}
left++;
}
}
}
return ret;
}
