题解 | #数组中相加和为0的三元组#

• 题目：给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。条件一：三元组（a、b、c）中的元素必须按非降序排列。（即a≤b≤c）条件二：解集中不能包含重复的三元组。
• 标签：数组 双指针
• 方法：首先每一格三元组要有序，因此用Arrays.sort(num)堆整个数组排序；遍历整个数组从0~len-2，作为第一个数字；然后定义双指针left,right一前一后，判断三个值的和与0的大小关系，若相等，则加入数组中，并将小数组加入大数组。
• 难点在于：【条件二】如何去除答案中的重复三元组，如0,0,0,0,0和-1,-1,0,1,1这种，因此需要在遍历和循环的过程中对三个指针指向的数字进行判断，如果nums[i]==nums[i-1]，跳过本次遍历；如果nums[left]==nums[left+1]那么left++；同理，如果nums[right]==nums[righr-1]那么right--。同时再注意边界条件就好了。

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        Arrays.sort(num);
        int len = num.length;
        for (int i = 0; i < len - 2; i++) {

            if (num[i] > 0) break;
            if (i > 0 && num[i] == num[i - 1]) continue; // 去重重复的三元组

            int left = i + 1, right = len - 1;
            while (left < right) {
                if (num[left] + num[right] == -num[i]) {
                    ArrayList<Integer> resS = new ArrayList<>();

                    resS.add(num[i]);
                    resS.add(num[left]);
                    resS.add(num[right]);
                    res.add(resS);
                    left++;
                    right--;

                    while (left < right && num[left] == num[left - 1]) {
                        left++;
                    }
                    while (left < right && num[right] == num[right + 1]) {
                        right--;
                    }
                }
                while (left < right && num[left] + num[right] > -num[i])
                    right--;
                while (left < right && num[left] + num[right] < -num[i])
                    left++;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] num = new int[]{0, 0, 0, 0, 0};
        Solution s = new Solution();
        ArrayList<ArrayList<Integer>> res = s.threeSum(num);
        for (ArrayList<Integer> re : res) {
            for (Integer integer : re) {
                System.out.print(integer + " ");
            }
            System.out.println(',');
        }
    }
}