LeetCode解题之十二:三数之和

本文阅读 1 分钟
首页 代码,Java 正文

题目

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

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

示例

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解答

public class Solution { 


    public List<List<Integer>> threeSum(int[] nums) { 
        List<List<Integer>> results = new ArrayList<>();
        
        if (nums == null || nums.length < 3) { 
            return results;
        }
        
        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 2; i++) { 
           
            if (i > 0 && nums[i] == nums[i - 1]) { 
                continue;
            }

            int left = i + 1, right = nums.length - 1;
            int target = -nums[i];
            
            twoSum(nums, left, right, target, results);
        }
        
        return results;
    }
    
    public void twoSum(int[] nums,
                       int left,
                       int right,
                       int target,
                       List<List<Integer>> results) { 
        while (left < right) { 
            if (nums[left] + nums[right] == target) { 
                ArrayList<Integer> triple = new ArrayList<>();
                triple.add(-target);
                triple.add(nums[left]);
                triple.add(nums[right]);
                results.add(triple);
                
                left++;
                right--;
               
                while (left < right && nums[left] == nums[left - 1]) { 
                    left++;
                }
              
                while (left < right && nums[right] == nums[right + 1]) { 
                    right--;
                }
            } else if (nums[left] + nums[right] < target) { 
                left++;
            } else { 
                right--;
            }
        }
    }
}
本文为互联网自动采集或经作者授权后发布,本文观点不代表立场,若侵权下架请联系我们删帖处理!文章出自:https://blog.csdn.net/Diamond_Tao/article/details/100637979
-- 展开阅读全文 --
大白话讲解JDK源码系列:从头到尾再讲一遍ThreadLocal
« 上一篇 01-30
KillDefender 的 Beacon 对象文件 PoC 实现
下一篇 » 02-09

发表评论

成为第一个评论的人

热门文章

标签TAG

最近回复