【leetcode】15. 三数之和(medium)

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意:答案中不可以包含重复的三元组。

这题真的好难,试了好多方法,最后参考了代码随想录的解法:文章来源地址https://uudwc.com/A/9vGLm

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums.length<3) return res;
        // 排序,方便操作
        Arrays.sort(nums);
        for(int i=0;i<nums.length-2;i++){
            // 剪枝:已经排过序了,所以如果第一个值大于0,没有可行解
            if(nums[i]>0) return res;
            // 剪枝:如果当前元素和前一个元素一样,跳过即可,否则会有重复解
            if((i>0) && (nums[i-1]==nums[i])) continue;
            int left = i+1;
            int right = nums.length-1;
            while(left < right){
                // int sum = nums[i]+nums[left]+nums[right];
                if(nums[i]+nums[left]+nums[right] == 0){
                    res.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--;
                }
                else if(nums[i]+nums[left]+nums[right] < 0)
                    left++;
                else if(nums[i]+nums[left]+nums[right] > 0)
                    right--;
            }
        }
        return res;
    }
}

原文地址:https://blog.csdn.net/qq_42251120/article/details/132240742

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请联系站长进行投诉反馈,一经查实,立即删除!

h
上一篇 2023年08月12日 22:58
VS 远程开发调试环境搭建 简明教程
下一篇 2023年08月12日 23:03