每日题解:LeetCode 15. 三数之和

Author Avatar
清水雅然君 06月 13,2020

题目地址
个人博客地址

题目描述

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

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

示例:

给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解法

JAVA

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums == null || n < 3) {
            return result;
        }
        Arrays.sort(nums);
        for (int i = 0; i < n - 2; i++) { 
            //排序后只要负数a和b,c相加才能等于0,排序a>0.后面的b,c都>0
            if (nums[i] > 0) {
                break;
            }
            //去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = n - 1;
            while (left < right) {
                if (nums[left] + nums[right] + nums[i] < 0 || (left > i + 1 && nums[left] == nums[left - 1])) {
                    left++;
                } else if (nums[left] + nums[right] + nums[i] > 0 || (right < n - 1 && nums[right] == nums[right + 1])) {
                    right--;
                } else{
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[i]);
                    list.add(nums[left++]);
                    list.add(nums[right--]);
                    result.add(list);
                }
            }
        }
        return result;
    }
}

解题思路

排序 + 双指针

我们以-1, 0, 1, 2, -1, -4为例,题目要去a+b+c的和为0,首先肯定有一个数字为负数,我们可以先将数组进行排序-4,-1,-1,0,1,2
1.假设我们a为-4,我们从后面的-1,-1,0,1,2中找到a+b+c的数字,我们可以使用双指针,遍历直到我们找到合适的数字,等到双指标遍历结束后,依然不满足的
2.我们继续假设a=-1,继续寻找b和c,可以寻找到[-1, 0, 1],[-1, 0, 1], [-1, -1, 2],由于题目要求不重复的三元组,答案中,-1是两个不同下标的-1,那我们就需要在遍历过程进行去重,由于我们一开始进行了排序处理,只要对比双指针的当前值和上一个值的是否相同就就可以了,这里我们left表示左指针,right表示右指针,left和left-1,right和right+1的值比较,进行去重。
3.那我们需要遍历整个数组吗?由于a+b+c要求和为0,其中肯定有一个负数,由于我们开始进行了排序,只要遍历完负数就可以了
所以这题的关键点在 Arrays.sort(nums);

 if (nums[left] + nums[right] + nums[i] < 0 || (left > i + 1 && nums[left] == nums[left - 1])) {
left++;
}

如果nums[left] + nums[right] + nums[i] < 0 ,如果和小于0,说明需要寻找一个更大数字,那就left移动一位,同理(nums[left] + nums[right] + nums[i] > 0,我们就需要right移动一位,需要一个小点的数字。

for (int i = 0; i < n - 2; i++) {
            //排序后只要负数a和b,c相加才能等于0,排序a>0.后面的b,c都>0
            if (nums[i] > 0) {
                break;
            }
            //去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = n - 1;
            while (left < right) {
            //去重
                if (nums[left] + nums[right] + nums[i] < 0 || (left > i + 1 && nums[left] == nums[left - 1])) {
                    left++;
                } else if (nums[left] + nums[right] + nums[i] > 0 || (right < n - 1 && nums[right] == nums[right + 1])) {
                    right--;
                } else{
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[i]);
                    list.add(nums[left++]);
                    list.add(nums[right--]);
                    result.add(list);
                }
            }
        }

这题巧妙之处,就是利用排序的做法,降低了我们遍历选择的难度。