LeetCode15. 三数之和

一、题目描述

☆☆☆☆二、解法

思路：排序+对撞指针，注意需要去重。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        /**
         *  思路：排序 + 对撞指针
         *        时间复杂度 O(n^2)
         */
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length < 3) return res;
        Arrays.sort(nums); // 排序

        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) break; // 如果当前元素大于0，则三数之和一定大于0
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重
            int start = i + 1;
            int end = nums.length - 1;
            while (start < end) {
                int tempSum = nums[i] + nums[start] + nums[end];
                if (tempSum > 0) {
                    end --;
                }else if (tempSum < 0) {
                    start ++;
                }else {
                    // 如下方式去重超时
//                    List<Integer> list = new ArrayList<>();
//                    list = Arrays.asList(nums[i],nums[start],nums[end]); // 学习asList的用法
//                    if (!res.contains(list)) {
//                        res.add(list);
//                    }
                    res.add(Arrays.asList(nums[i], nums[start], nums[end]));
                    while (start < end && nums[start] == nums[start + 1]) start ++; // 去重
                    while (start < end && nums[end] == nums[end - 1]) end --; //去重
                    start ++;  // 不加会死循环
                    end --;
                }
            }
        }
        return res;
    }
}