leetcode算法--三数之和之java实现

一、问题

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

例如:

给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[ [-1, 0, 1], [-1, -1, 2] ]

二、解题思路

最简单的方法自然是三重for循环, 暴力解法, 时间复杂度为O(n^3), 这是没法忍受的, leetcode提交也通过不了
大部分解法为排序 + 双指针的方法

• 由小到大排序
• 根据拉格朗日中值定理(我瞎说的)三个数之和等于0, 那么三个数由小到大排序, 依次连线, 必然有一条线经过0, 所以最小数 <= 0, 而另外两个数之和与最小数相反
• 另外两个数使用左右指针的方式解决

三数之和.png

三、代码

public List<List<Integer>> threeSum(int[] nums) {
    // 简单校验
    if (nums == null || nums.length < 3) {
        return new ArrayList<>();
    }
    // 排序
    Arrays.sort(nums);

    List<List<Integer>> list = new ArrayList<>();
    // 三个索引
    int start, left, right;
    // 1. 初始化, start从0开始, 最大不会超过倒数第三个数, 并且三个数全是正数绝对不可能相加等于0
    for (start = 0; start < nums.length - 2 && nums[start] <= 0; start++) {
        // 去重 如果当前数等于前一个数, 则当前数的组合小于等于前一个数的组合
        if (start > 0 && nums[start] == nums[start - 1]) {
            continue;
        }
        // 左索引从起始索引第二开始, 右索引从最有一个索引开始, 并且左索引必须小于右索引
        for (left = start + 1, right = nums.length - 1; left < right; ) {
            // 去重, 同上
            if (left > start + 1 && nums[left] == nums[left - 1]) {
                left++;
                continue;
            }
            // 去重, 同上
            if (right < nums.length - 1 && nums[right] == nums[right + 1]) {
                right--;
                continue;
            }

            int twoSum = nums[left] + nums[right];
            // 两数之和 与 起始数的相反数比较大小
            if (twoSum > -nums[start]) {
                right--;
            } else if (twoSum < -nums[start]) {
                left++;
            } else {
                List<Integer> subList = new ArrayList<>();
                subList.add(nums[start]);
                subList.add(nums[left]);
                subList.add(nums[right]);
                list.add(subList);
                right--;
                left++;
            }
        }
    }
    return list;
}

4、类似问题--最接近的三数之和

public int threeSumClosest(int[] nums, int target) {
    // 简单校验
    if (nums == null || nums.length < 3) {
        return -1;
    }
    // 排序
    Arrays.sort(nums);

    int minDiff = Integer.MAX_VALUE;
    int closestSum = 0;

    // 三个索引
    int start, left, right;
    // 1. 初始化, start从0开始, 最大不会超过倒数第三个数
    for (start = 0; start < nums.length - 2; start++) {
        // 去重 如果当前数等于前一个数, 则当前数的组合小于等于前一个数的组合
        if (start > 0 && nums[start] == nums[start - 1]) {
            continue;
        }
        // 左索引从起始索引第二开始, 右索引从最有一个索引开始, 并且左索引必须小于右索引
        for (left = start + 1, right = nums.length - 1; left < right; ) {
            // 去重, 同上
            if (left > start + 1 && nums[left] == nums[left - 1]) {
                left++;
                continue;
            }
            // 去重, 同上
            if (right < nums.length - 1 && nums[right] == nums[right + 1]) {
                right--;
                continue;
            }

            int threeSum = nums[start] + nums[left] + nums[right];
            int diff = Math.abs(threeSum - target);
            if (diff < minDiff) {
                minDiff = diff;
                closestSum = threeSum;
            }

            // 两数之和 与 起始数的相反数比较大小
            if (threeSum > target) {
                right--;
            } else if (threeSum < target) {
                left++;
            } else {
                return closestSum;
            }
        }
    }
    return closestSum;
}

---

参考

1. 15. 三数之和
2. 三数之和（排序+双指针，易懂图解）
   

---

1. 15. 三数之和 - 力扣（LeetCode） ↩