当前位置：首页 > article >正文

leetcode hot100 之【LeetCode 15. 三数之和】 java实现

article 2024/10/19 14:24:01

LeetCode 15. 三数之和

题目描述

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

注意：

答案中的三元组可以按任意顺序组织。
在 nums 中，除了同一个三元组中的元素可以重复外，不可以有重复的三元组。

示例 1：

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

示例 2：

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

示例 3：

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

Java 实现解法

方法一：排序 + 双指针

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums); // 首先对数组进行排序
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) break; // 如果当前数字大于0，则后面的数字之和一定大于0
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 跳过重复的数字
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < 0) {
                    left++;
                } else if (sum > 0) {
                    right--;
                } else {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while (left < right && nums[left] == nums[left + 1]) left++; // 跳过重复的数字
                    while (left < right && nums[right] == nums[right - 1]) right--; // 跳过重复的数字
                    left++;
                    right--;
                }
            }
        }
        return result;
    }
}

解题思路

排序：首先对数组进行排序，这样可以通过一次遍历来找到所有可能的三元组，并且可以方便地跳过重复的解。
固定第一个数：遍历数组，对于每个元素 nums[i]，我们尝试找到两个其他元素，使得它们与 nums[i] 的和为 0。
双指针：对于每个 nums[i]，我们使用两个指针 left 和 right 分别指向 i + 1 和 nums.length - 1。这样，我们可以在这个范围内寻找和为 -nums[i] 的两个数。
跳过重复解：如果在数组中找到了相同的数字，跳过它们以避免重复的三元组。
更新指针：如果三数之和小于 0，则移动 left 指针；如果大于 0，则移动 right 指针；如果等于 0，则找到了一个解，并更新指针跳过重复的数字。