LeetCode 三数之和【双指针】

偏执的太偏执、 2022-09-09 06:11 166阅读 0赞

# 三数之和 #

给你一个包含 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]
    输出：[]

提示：

0 <= nums.length <= 3000
    -105 <= nums[i] <= 105

# 解题思路 #

排序 + 双指针

/** * 时间复杂度： O（n^2） * 空间复杂度: O(1) */
        public List<List<Integer>> threeSum(int[] nums) { 
            //1 排序
            Arrays.sort(nums);
            List<List<Integer>> rs = new ArrayList<>();
            //2 遍历
            for (int i = 0; i < nums.length; i++) { 
                //如果最小值大于0
                if (nums[i] > 0) { 
                    break;
                }
                //值重复
                if (i > 0 && nums[i] == nums[i - 1]) { 
                    continue;
                }
    
                //双指针
                int lp = i + 1;
                int rp = nums.length - 1;
                while (lp < rp) { 
                    int sum = nums[lp] + nums[rp] + nums[i];
                    if (sum == 0) { 
                        //找到
                        List<Integer> tempList = Arrays.asList(nums[i], nums[lp], nums[rp]);
                        rs.add(tempList);
                        lp++;
                        rp--;
                        //取消重复
                        while (lp < rp && nums[lp] == nums[lp - 1]) lp++;
                        while (lp < rp && nums[rp] == nums[rp + 1]) rp--;
    
                    } else if (sum > 0) { 
                        rp--;
                    } else { 
                        lp++;
                    }
    
                }
            }
            return rs;
        }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/c8deda43ffed4a18bcb07d7541a4731f.png