leetcode 15 三数之和

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

注意：答案中不可以包含重复的三元组。
示例 1：

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

示例 2：

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

示例 3：

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

排序 + 双指针

思路：如何去除重复解。

算法流程：

1. 特判，对于数组长度 n，如果数组为 null或者数组长度小于 3，返回 []。
2. 对数组进行排序。
3. 遍历排序后数组：

• 若 nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果。
• 对于重复元素：跳过，避免出现重复解
• 令左指针 L=i+1，右指针 R=n−1，当 L<R 时，执行循环：
  • 当 nums[i]+nums[L]+nums[R]==0执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,RL,RL,R 移到下一位置，寻找新的解
  • 若和大于 0，说明 nums[R]太大，R 左移
  • 若和小于 0，说明 nums[L]太小，L右移
    代码

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList();
        int len  = nums.length;
        //当前数组的长度为空，或者长度小于3时，直接退出
        if(nums == null || len < 3){
            return res;
        }
        Arrays.sort(nums);//将数组进行排序
        for(int i = 0; i < len; ++i){
            if(nums[i] > 0) {// 如果遍历的起始元素大于0，就直接退出
                return res;
            }
            //去重
            if(i > 0 && nums[i] == nums[i-1]) continue;
            //设置左右指针
            int L = i + 1;
            int R = len - 1;
            while(L < R){
                int sum = nums[i] + nums[L] + nums[R];
                if(sum == 0){ //如果等于0，将结果对应的索引位置的值加入结果集中
                    List<Integer> list = new ArrayList();
                    list.add(nums[i]);
                    list.add(nums[L]);
                    list.add(nums[R]);
                    res.add(list);
                    //去重
                    while(L < R && nums[L] == nums[L + 1]){
                        L++;
                    }
                    while(L < R && nums[R] == nums[R - 1]){
                        R--;
                    }
                    //将左指针右移，将右指针左移。
                    L++;
                    R--;
                }
                else if(sum < 0){
                    L++;
                }
                else{
                    R--;
                }
            }
        }
        return res;
    }
}

最后

以上就是瘦瘦滑板为你收集整理的leetcode 15 三数之和的全部内容，希望文章能够帮你解决leetcode 15 三数之和所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。