c语言双指针求三数之和,leetcode三数之和--双指针

题目链接：三数之和

题目描述：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：

[

[-1, 0, 1],

[-1, -1, 2]

]

题目分析：关键在于不重复，那么为了不重复，可以先对数组排序，同时在遍历过程中控制循环下标和相邻元素是否相等的判断，达到去重的目的。继续说，由于三数之和是固定的，那么我们在知道其中两个数之后，第三个数是确定的，所以我们可以固定一个数，然后枚举另外两个数。另外两个数和是确定的，只要其中一个增大，另外一个必定减少，因此，可以采用双指针进行双向并行遍历，减少时间复杂度。

对于本题「双指针」，当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法，将枚举的时间复杂度从 O(N2)减少至O(N)。为什么是 O(N) 呢？这是因为在枚举的过程每一步中，「左指针」会向右移动一个位置(也就是题目中的 b)，而「右指针」会向左移动若干个位置，这个与数组的元素有关，但我们知道它一共会移动的位置数为O(N)，均摊下来，每次也向左移动一个位置，因此时间复杂度为 O(N)。

代码：

class Solution {

public List> threeSum(int[] nums) {

List> res = new ArrayList<>();

Arrays.sort(nums);

int i = 0,l ,r,sum;

while(i < nums.length-2&&nums[i]<=0){

l = i+1;

r = nums.length-1;

while(l

sum = nums[l]+nums[i]+nums[r];

if(sum==0){

res.add(Arrays.asList(nums[l++],nums[i],nums[r--]));

//去重

while(l

while(l

}else if(sum<0){

l++;

}else

r--;

}

i++;

//去重

while(i

}

return res;

}

}

补充一个类似的题目：

最接近的三数之和

与这个题目几乎如出一辙的思路

class Solution {

public int threeSumClosest(int[] nums, int target) {

Arrays.sort(nums);

int ans = 1000000;

for(int i = 0;i < nums.length;i++){

if(i>0&&nums[i]==nums[i-1]) continue;

int j = i + 1, k = nums.length-1;

while(j

int sum = nums[i]+nums[j]+nums[k];

if(sum==target) return target;

if(Math.abs(sum-target)

ans = sum;

if(sum>target){

k--;

while(j

}else{

j++;

while(j

}

}

}

return ans;

}

}