算法日记-LeetCode-15-三数之和

2023-07-09

字数统计: 522字 | 阅读时长≈ 2分

算法日记-LeetCode-15-三数之和

题目大意

给定一个无序数组，数组长度[3, 3000]，求出所有满足nums[i] + nums[j] + nums[k] = 0的三元组，且i != j, j != k。

示例：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

解题思路

循环

通过三重循环遍历数组，找到满足条件的值，三重循环容易超时

排序 + 双指针

首先对数组进行排序，排序后可采用双指针的方式缩小范围得到目标值。

对排序后的数组进行遍历，如果nums[idx] > 0，则之后肯定不存在满足条件的值，此时可以直接返回结果，且题目要求不重复，故需要对重复的元素进行跳过。

从i开始，令left = idx + 1, rigth = n - 1，则存在以下三种情况：

nums[idx] + nums[left] + nums[right] = 0 ：即为目标解
nums[idx] + nums[left] + nums[right] > 0 : nums[right] 过大， right 左移；
nums[idx] + nums[left] + nums[right] < 0 : nums[left] 过小， left 右移

直到left与right相遇。

代码

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList<>();
        int idx = 0, n = nums.length;
        while (idx < n) {
            if (nums[idx] > 0) {
                return list;
            }
            while (idx > 0 && idx < n && nums[idx] == nums[idx - 1]) {
                idx++;
            }
            int left = idx + 1, right = n - 1;
            while(left < right) {
                if (nums[idx] + nums[left] + nums[right] == 0) {
                    List<Integer> ans = new ArrayList<>();
                    ans.add(nums[idx]);
                    ans.add(nums[left]);
                    ans.add(nums[right]);
                    list.add(ans);
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    left++;
                    right--;
                } else if (nums[idx] + nums[left] + nums[right] > 0) {
                    right--;
                } else if (nums[idx] + nums[left] + nums[right] < 0) {
                    left++;
                }
            }
            idx++;
        }
        return list;
    }
}

本文作者： Naskete
本文链接： https://Naskete.github.io/2023/07/09/algorithm/算法日记-LeetCode-15.三数之和II/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！