LeetCode-数组-三数之和

ゝ一世哀愁。 2022-01-20 05:25 161阅读 0赞

## 题目描述 ##

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

注意：答案中不可以包含重复的三元组。 [习题原文][Link 1]

## 解题思路 ##

> 求三数之和为 0, nums\[i\] + nums\[j\] + nums\[k\] = 0 可以转换为求两个数之和，也即是 nums\[i\] + nums\[j\] = -nums\[k\]; 那么就可以通过指针移动去查找满足公式的数字，而为了方便控制指针的移动，前提是一组数字是有序的。

那么大概的解题思路如下:

*  对数组排序
 *  定义三个指针 i, left, right; 指针 i 指向的是求和项，指针 left, right 分别指向数组的头部和尾部
 *  当 -nums\[i\] = nums\[left\] + nums\[right\] 时满足公式，指针 left, right 继续向中部移动
 *  当 -nums\[i\] > nums\[left\] + nums\[right\] 时指针 left 向中部移动
 *  当 -nums\[i\] < nums\[left\] + nums\[right\] 时指针 righr 向中部移动
 *  当指针 left，right 交叉时停止移动，指针 i 向下移动，指针 left, right 重置

其流程如下图所示:

## 实现 ##

public static List<List<Integer>> solution(int[] nums) {
        // 排序
        Arrays.sort(nums);
    
        List<List<Integer>> rs = new ArrayList<>();
    
        int i = 0, left = 1, right = nums.length - 1;
    
        while (i < nums.length - 2) {
            while (true) {
                // 左右指针交叉退出
                if (right <= left) {
                    break;
                }
    
                if (-nums[i] == nums[left] + nums[right]) {
                    rs.add(Arrays.asList(nums[i], nums[left], nums[right]));
    
                    // 过滤同一结果内重复的数字
                    // 左右指针继续向中间移动
                    while (true) {
                        if (left >= nums.length - 1) {
                            break;
                        }
    
                        if (nums[left] != nums[left + 1]) {
                            left++;
                            break;
                        } else {
                            left++;
                        }
                    }
    
                    while (true) {
                        if (right <= 0) {
                            break;
                        }
    
                        if (nums[right] != nums[right - 1]) {
                            right--;
                            break;
                        } else {
                            right--;
                        }
                    }
    
                    continue;
                }
    
                if (-nums[i] <= nums[left] + nums[right]) {
                    right--;
                    continue;
                }
    
                if (-nums[i] > nums[left] + nums[right]) {
                    left++;
                    continue;
                }
            }
    
            // 过滤同一结果值的数字
            while (true) {
                if (i >= nums.length - 1) {
                    break;
                }
    
                if (nums[i] != nums[i + 1]) {
                    i++;
                    break;
                } else {
                    i++;
                }
            }
    
            //i++;
            left = i + 1;
            right = nums.length - 1;
        }
    
        return rs;
    }
    复制代码

[参见原文][Link 2]

[Link 1]: https://link.juejin.im?target=https%3A%2F%2Fleetcode-cn.com%2Fproblems%2F3sum%2F
[Link 2]: https://link.juejin.im?target=https%3A%2F%2Fwww.hxlzpnyist.site%2F2019%2F02%2F24%2FLeetCode-%25E6%2595%25B0%25E7%25BB%2584-%25E4%25B8%2589%25E6%2595%25B0%25E4%25B9%258B%25E5%2592%258C%2F