Leetcode-15-三数之和

15. 三数之和

难度中等3274收藏分享切换为英文接收动态反馈

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = []
输出：[]

示例 3：

输入：nums = [0]
输出：[]

提示：

• 0 <= nums.length <= 3000
• -105 <= nums[i] <= 105

15. 3Sum

Medium

102481053Add to ListShare

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.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Example 2:

Input: nums = []
Output: []

Example 3:

Input: nums = [0]
Output: []

Constraints:

• 0 <= nums.length <= 3000
• -105 <= nums[i] <= 105

排序 + 双指针

解决三和问题，

我们先探讨2和的问题，就是给定一个数组，区数组中2个数，加起来定于指定的值K

image-20210425095937074

两数之和

第一步，我们先给数组排序，让数组有序

第二步，定义L指针=0 R=arr.length-1

• 判断 arr[L]+Arr[R]> target R--
• 判断 arr[L]+Arr[R]< target L--
• 判断 arr[L]+Arr[R]== target 收集答案 L++

    // nums已经有序了
    // nums[begin......]范围上，找到累加和为target的所有二元组
    public static List<List<Integer>> twoSum1(int[] nums, int begin, int target) {
        int L = begin;
        int R = nums.length - 1;
        List<List<Integer>> ans = new ArrayList<>();
        while (L < R) {
            if (nums[L] + nums[R] > target) {
                R--;
            } else if (nums[L] + nums[R] < target) {
                L++;
            } else {
                if (L == begin || nums[L - 1] != nums[L]) {
                    List<Integer> cur = new ArrayList<>();
                    cur.add(nums[L]);
                    cur.add(nums[R]);
                    ans.add(cur);
                }
                L++;
            }
        }
        return ans;
    }

在二和能够解决的基础上，我们来解决三和问题。

排序 + 双指针

算法流程：

1. 特判，对于数组长度 n，如果数组为 NULL 或者数组长度小于 3，返回[] [][]。
2. 对数组进行排序。
3. 遍历排序后数组：

排序:[-1,0,1,2,-1,-4]

排序

image-20210425101204637

image-20210425101402033

image-20210425101900868

class Solution {
    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        // 第一个数选了i位置的数
        for (int i = 0; i < nums.length - 2; i++) {
            if (i == 0 || nums[i - 1] != nums[i]) {
                List<List<Integer>> nexts = twoSum1(nums, i + 1, -nums[i]);
                for (List<Integer> cur : nexts) {
                    cur.add(0, nums[i]);
                    ans.add(cur);
                }
            }
        }
        return ans;
    }

    // nums已经有序了
    // nums[begin......]范围上，找到累加和为target的所有二元组
    public static List<List<Integer>> twoSum1(int[] nums, int begin, int target) {
        int L = begin;
        int R = nums.length - 1;
        List<List<Integer>> ans = new ArrayList<>();
        while (L < R) {
            if (nums[L] + nums[R] > target) {
                R--;
            } else if (nums[L] + nums[R] < target) {
                L++;
            } else {
                if (L == begin || nums[L - 1] != nums[L]) {
                    List<Integer> cur = new ArrayList<>();
                    cur.add(nums[L]);
                    cur.add(nums[R]);
                    ans.add(cur);
                }
                L++;
            }
        }
        return ans;
    }
}

image-20210425102111550