（双指针）Java 求解三数之和

小咪咪 2023-01-19 08:23 5阅读 0赞

### 文章目录 ###

*   *  一、题目
     *  二、双指针法解析
     *  三、代码
     *  四、总结

## 一、题目 ##

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

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

## 二、双指针法解析 ##

首先对数组 nums 排序，然后 i 从0开始遍历数组，同时定义一个 left 在 i+1 位置，定义一个right 在数组末尾位置

令 `sum = nums[i] + nums[left] + nums[right];`

如果 nums\[i\] 大于0 则遍历结束：因为已经排过序，如果nums\[i\]>0，则sum一定大于0，所以遍历结束

如果 sum=0，则记录三元素

如果 sum>0，说明三元素和过大，则 right 指针左移

如果 sum<0，说明三元素和过小，则 left 指针右移

直到 left 和 right 相遇

## 三、代码 ##

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    class Solution { 
        public List<List<Integer>> threeSum(int[] nums) { 
            List<List<Integer>> lists = new ArrayList<>();
            List<Integer> list;
            Arrays.sort(nums);
            for (int i = 0; i < nums.length; i++) { 
                //排序之后，如果三个元素中的第一个已经大于0，则组合无论如何无法凑成三元组，直接返回结果即可
                if (nums[i] > 0) { 
                    return lists;
                }
                //去重：nums[i] == nums[i - 1]
                if (i > 0 && nums[i] == nums[i - 1]) { 
                    continue;
                }
                int left = i + 1;
                int right = nums.length - 1;
                while (left < right) { 
                    int sum = nums[i] + nums[left] + nums[right];
                    if (sum > 0) { 
                        right--;
                    } else if (sum < 0) { 
                        left++;
                    } else { 
                        list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[left]);
                        list.add(nums[right]);
                        lists.add(list);
                        //去重逻辑放在找到一个三元组之后
                        while (right > left && nums[left] == nums[left + 1]) { 
                            left++;
                        }
                        while (right > left && nums[right] == nums[right - 1]) { 
                            right--;
                        }
                        //找到答案时，双指针开始收缩
                        right--;
                        left++;
                    }
                }
            }
            return lists;
        }
    }

精简：

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

## 四、总结 ##

双指针：通过前后两个指针不断向中间逼近，在一个 for 循环下完成两个 for 循环的工作