LeetCode 15. 三数之和

15. 3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

解法思路：

// a + b = -c (target)

// 1. 暴力求解：三重循环 O(n^3)

// 2. hash表来记录 a, b, a+b = -c

// 3. 双指针：左右下标往中间推进

?法一：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 暴力求解：三重循环，O(n^3)
        Set set = new HashSet<>();
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[k]);
                        Collections.sort(list);
                        set.add(list);
                    }
                }
            }
        }
        return new ArrayList<>(set);
    }
}

// 小小优化
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 暴力求解：三重循环，O(n^3)
        Arrays.sort(nums);
        Set set = new HashSet<>();
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        set.add(Arrays.asList(nums[i], nums[j], nums[k]));                    }
                }
            }
        }
        return new ArrayList<>(set);
    }
}

法二：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // Time: O(n^2)
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        if (nums.length < 3 || nums[0] > 0) {
            return res;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) {
                break;
            }
            for (int j = i + 1; j < nums.length - 1; j++) {
                int target = -1 * (nums[i] + nums[j]);
                if (map.containsKey(target) && map.get(target) > j) {
                    res.add(Arrays.asList(nums[i], nums[j], target));
                }
                j = map.get(nums[j]);
            }
            i = map.get(nums[i]);
        }
        return res;
    }
}

法三：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // Time: O(n^2)
        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList<>();
        if (nums.length < 3 || nums[0] > 0) {
            return list;
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    list.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    int lastLeftCur = nums[left];
                    int lastRightCur = nums[right];

                    while (left < right && nums[left] == lastLeftCur) {
                        left++;
                    }
                    while (left < right && nums[right] == lastRightCur) {
                        right--;
                    }
                }
            }
        }
        return list;
    }
}

// 另一个版本
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // Time: O(n^2)
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int k = 0; k < nums.length - 2; ++k) {
            if (nums[k] > 0) break;
            if (k > 0 && nums[k] == nums[k - 1]) continue;
            int i = k + 1;
            int j = nums.length - 1;
            while (i < j) {
                int sum = nums[k] + nums[i] + nums[j];
                if (sum < 0) {
                    while (i < j && nums[i] == nums[++i]);
                } else if (sum > 0) {
                    while (i < j && nums[j] == nums[--j]);
                } else {
                    res.add(new ArrayList<>(Arrays.asList(nums[k], nums[i], nums[j])));
                    while (i < j && nums[i] == nums[++i]);
                    while (i < j && nums[j] == nums[--j]);
                }
            }
        }
        return res;
    }
}