【leetcode】15.整数数组，三数之和为0

墨蓝 2022-01-30 13:53 144阅读 0赞

打卡第1周

# 题目： #

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

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

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
    
    满足要求的三元组集合为：
    [
      [-1, 0, 1],
      [-1, -1, 2]
    ]

# 解题思路： #

1.先给数组排序

2.三个数字，确定一个数，即循环数组的数。sum-c=0，这样只要让a+b=sum即可

3.如果，a+b>sum，将b往右（小）移动；a+b<sum，将a往右（大）移动

4.如果i=i+1；即相邻元素重复，跳过，不输出

# 代码： #

package test.com;
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    public class Solution {
        public static void main(String[] args) {
            Solution solution=new Solution();
            int[] a={-1,0,1,2,-1,-4,5,6,3};
            solution.threeSum(a);
        }
        public List<List<Integer>> threeSum(int[] ints) {
            //排序
            Arrays.sort(ints);
    
            List<List<Integer>> out = new ArrayList<>();
    
            for (int i = 0; i < ints.length - 2; i++) {
                if (i == 0 || ( ints[i] != ints[i - 1])) {
    
                    int l = i + 1, r = ints.length - 1, sum = 0 - ints[i];
                    while (l < r) {
                        //sum=0-a[i]
                        if (ints[l] + ints[r] == sum) {
                            out.add(Arrays.asList(ints[l],ints[i],ints[r]));
                            //重复元素，跳过
                            while (l < r && ints[l] == ints[l + 1]) l++;
                            while (l < r && ints[r] == ints[r - 1]) r--;
                            l++;
                            r--;
                        } else if (ints[l] + ints[r] < sum) {
                            //小于，左边右移一位
                            while (l < r && ints[l] == ints[l + 1]) l++;
                            l++;
                        } else {
                            //大于，右边左移一位
                            while (l < r && ints[r] == ints[r - 1]) r--;
                            r--;
                        }
                    }
                }
            }
            System.out.println(out);
            return out;
        }
    }

# 输出： #

\[\[-1, -4, 5\], \[1, -4, 3\], \[-1, -1, 2\], \[0, -1, 1\]\]