[LeetCode]15. 三数之和

题目

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

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

示例：

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

• 思路：升序排序，遍历操作数1(当它>=0)，
  {用双指针l、r遍历右侧，当sum=0,放入集合；当sum>0,r--; 当sum<0，l++

• 特判：数组长度小于3

• 注意：对三个操作数的去重

相关

Arrays.sort(arr[]); //对原数组排序
Arrays.asList(elm1,elm2,elm3...) //return new ArrayList(elm1,elm2,elm3..); //返回承装这些元素的ArrayList

代码

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

        Arrays.sort(nums);
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] > 0) { // 最小数>0则结束循环
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1]) { // 去重
                continue;
            }

            int l = i + 1;
            int r = nums.length - 1;
            int sum = 0;
            while (l < r) {
                sum = nums[i] + nums[l] + nums[r];
                if (sum == 0) {
                    ansList.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    while (l+1 < r && nums[l] == nums[l + 1]) {// 去重
                        l++;
                    }
                    while (l < r-1  && nums[r] == nums[r - 1]) {// 去重
                        r--;
                    }
                    l++;
                    r--;
                } else if (sum < 0) {
                    l++;
                } else {
                    r--;
                }
            }
        }
        return ansList;
    }
}

[LeetCode]15. 三数之和

原文：https://www.cnblogs.com/coding-gaga/p/12267837.html