leetcode 热题 100_三数之和
题解一：
双指针遍历：暴力解法的三层遍历会超时，因此需要优化遍历的过程。首先是需要对结果进行去重，这里采用排序+跳过重复值的做法，在指针遍历时跳过已经遍历过的相同值。在第一层循环确定第一个值后，剩下两个符合要求的值一定是在其后相继出现的，因此可以用双指针从两侧逼近寻找符合的值，下面附上官方提供的伪代码（来源. - 力扣（LeetCode））
nums.sort() for first = 0 .. n-1if first == 0 or nums[first] != nums[first-1] then// 第三重循环对应的指针third = n-1for second = first+1 .. n-1if second == first+1 or nums[second] != nums[second-1] then// 向左移动指针，直到 a+b+c 不大于 0while nums[first]+nums[second]+nums[third] > 0third = third-1// 判断是否有 a+b+c==0check(first, second, third)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> lists = new ArrayList<>();Arrays.sort(nums);int len = nums.length;for (int i = 0; i < len; i++) {if (i == 0 || nums[i] > nums[i - 1]) {int right = len - 1;for (int left = i + 1; left < right; left++) {if (left == i + 1 || nums[left] > nums[left - 1]) {while (right > left + 1 && nums[left] + nums[right] + nums[i] > 0) {right--;}if (nums[left] + nums[right] + nums[i] == 0) {List<Integer> list = new ArrayList<>();list.add(nums[i]);list.add(nums[left]);list.add(nums[right]);lists.add(list);}}}}}return lists;}
}