【LeetCode】15. 三数之和

可以用三层循环的方法，O(n^3)

改进的三层循环：先进行排序，第二层和第三层循环采用两指针相遇问题。这样，复杂度为O(n^2)

/**
 * @Auther: Mason
 * @Date: 2020/07/14/9:43
 * @Description:
 */
public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int len = nums.length;
        // 首先进行升序排列
        Arrays.sort(nums);
        List<List<Integer>> res = new LinkedList<>();
        int third;
        int sum;
        OUT:
        for (int i = 0; i < len - 2; i++) { // 第一层循环
            if (i >= 1 && nums[i] == nums[i - 1]) continue;
            third = len - 1;// 第三个遍历的初始指针位置。
            for (int j = i + 1; j < len - 1; j++) { // 第二层循环
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                sum = nums[i] + nums[j];
                while (third > j && sum + nums[third] > 0) third--;
                if (third == j) continue OUT;
                if (sum + nums[third] == 0) {
                    LinkedList<Integer> tmp = new LinkedList<>();
                    tmp.add(nums[i]);
                    tmp.add(nums[j]);
                    tmp.add(nums[third]);
                    res.add(tmp);
                }
            }
        }
        return res;
    }
}