leetcode 15.三数之和 JAVA 双指针法

题目

思路

双指针法 + 去重

为啥要去重呢？因为题目中说了要返回不重复的三元组。拿示例1来看，（-1，0，1）和（0，1，-1）虽然都等于0，但其实它们里面的数都是一样的，最后只输出一个即可。

先说双指针法：

变量i用来从左到右遍历数组。然后设置一个left指针和一个right指针，分别指向 nums[i+1]和 nums[nums.length-1]。i的这个循环相当于固定第一个数，找出剩下两个数。

为了方便后续的说明，将i指向的元素称为a,left指向的为b,right指向的为c,我们目标是a+b+c=0

另外在开始前的一个重要的操作是要对数组进行排序（从小到大排序）

如果 nums[i]+nums[left]+nums[right] < 0 了，那么我们让left++ ,这是因为我们已经从小到大排好序了，现在sum<0，我们想让sum更大一些， i是固定的了，所以只能让left往左移
如果nums[i]+nums[left]+nums[right] > 0 了，我们就让right–，理由类比上面。
如果当前nums[i]+nums[left]+nums[right] 正好等于0了，我们将这三个数记录下来。然后left++,right–,寻找下一个三元组。

15.三数之和

去重：

分为三部分去重：

a的去重：

如果nums[i]==nums[i-1],则我们该找下一个i了。
为啥呢？举个例子 -2，-2，0，0，1，1，2，4 当指向第一个-2的时候，我们经过双指针法，已经找到了-2是第一个数的所有等于0的三元组了。这时候我们要进入下一个循环了，i指向了第二个-2,很明显这时候再进行双指针法找到的所有满足sum=0的三元组，都会包含在第一个-2的三元组的结果里。

b和c去重：

b的去重。nums[left+1]==nums[left]
c的去重。nums[right-1]==nums[right]

代码

//没有去重import java.lang.reflect.Array;
import java.util.Arrays;//leetcode submit region begin(Prohibit modification and deletion)
class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> res = new ArrayList<>();//对数组从小到大进行排序Arrays.sort(nums);for (int i = 0; i < nums.length; i++) {if (nums[i] > 0)break;int left = i + 1;int right = nums.length - 1;while (right > left) {int sum = nums[i] + nums[left] + nums[right];if (sum > 0) {right--;} else if (sum < 0) {left++;} else {res.add(Arrays.asList(nums[i], nums[left], nums[right]));left++;right--;}}}return res;}
}
//leetcode submit region end(Prohibit modification and deletion)

//去重import java.lang.reflect.Array;
import java.util.Arrays;//leetcode submit region begin(Prohibit modification and deletion)
class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> res = new ArrayList<>();//对数组从小到大进行排序Arrays.sort(nums);for (int i = 0; i < nums.length; i++) {//如果a就大于0了，后面的数都大于等于a，肯定sum不等于0if (nums[i] > 0)break;//对a去重if (i > 0 && nums[i] == nums[i - 1]) {continue;}int left = i + 1;int right = nums.length - 1;while (right > left) {int sum = nums[i] + nums[left] + nums[right];if (sum > 0) {right--;} else if (sum < 0) {left++;} else {res.add(Arrays.asList(nums[i], nums[left], nums[right]));//对b和c去重while (right > left && nums[left] == nums[left + 1]) left++;while (right > left && nums[right] == nums[right - 1]) right--;//找到一个三元组后，继续寻找下一个三元组left++;right--;}}}return res;}
}
//leetcode submit region end(Prohibit modification and deletion)