7.《双指针篇》---⑦三数之和（中等偏难）

题目传送门 

方法一：双指针

1.新建一个顺序表用来返回结果。并排序数组。

2.for循环 i 从第一个数组元素遍历到倒数第三个数。

3.如果遍历过程中有值大于0的则break； 

4.定义左右指针,以及target。int left = i + 1, right = n - 1; int target = -nums[i];

5.类似两数之和。比较int sum = nums[l] + nums[r] 与 target的大小

注意：

1.不能返回重复的数组。因此我们还需要排除重复的。

2.排序之后。在sum = target的时候。我们进行 left 和 right的排重。

3.在 i++ 之后我们进行 num[i] 这个元素的排重。

注意：

排重的时候双指针排重记得 left < right。并且num【i】排重的时候注意 i<n-1。

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> ret = new ArrayList<>();Arrays.sort(nums);int n = nums.length-1;for(int i = 0; i < n-1; ){if(nums[i] > 0){break;}int left = i + 1;int right = n;int target = -nums[i];while(left < right){int sum = nums[left] + nums[right];if(sum == target){ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right])));left++;right--;while(left < right && nums[left] == nums[left-1]){left++;}while(left < right && nums[right] == nums[right+1]){right--;}}else if(sum < target){left++;}else{right--;}}i++;while(i<n-1 && nums[i] == nums[i-1]){i++;}}return ret;}
}

 复杂度分析