三数之和

题目信息

给你一个包含 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]
输出：[]

解题思路

1. 暴力破解：嵌套三层循环，遍历每一个三个元素的组合，判断nums[i] + nums[j] + nums[k] = 0 ，然后去除重复组合，时间复杂度O(n^3)，空间复杂度O(1)
2. 无效操作分析：
   1. 重复组合会被计算三遍
   2. 第三层嵌套可使用前两个值替换 nums[k] = -nums[i] - nums[j]
3. 优化方法：观察分析发现只有拥有小于0的元素的组合才有可能组合出满足表达式的结果
4. 考虑边界
5. 编码实现

代码

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length < 3) {
            return ans;
        }
        // 将数组从小到大排序
        Arrays.sort(nums);
        // 如果最小的元素都大于0，那么不可能出现能满足条件的组合
        // 同理最大的元素都小于0，也不可能出现满足条件的组合
        int count = nums.length;
        if (nums[0] > 0 || nums[count - 1] < 0) {
            return ans;
        }
        
        for (int first = 0; first < count; first++) {
            // 去掉重复的起始元素
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            // 获取最右端的初始指针和目标值
            int target = -nums[first];
            int third = count - 1;
            // 寻找第二个元素
            for (int second = first + 1; second < count; second++) {
                // 去掉第二个的重复的起始元素
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                while (second < third && nums[second] + nums[third] > target) {
                    third--;
                }
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    ans.add(list);
                }
            }
        }
        return ans;
    }
}

题目来源：力扣（LeetCode）
题目链接：https://leetcode-cn.com/problems/3sum

商业转载请联系官方授权，非商业转载请注明出处。