博客

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

首先看到这道题，我们先进行一下关键词过滤，分别是

【数组】【求和】【不重复】

其中 前两个关键词 都指向了针对数据问题的一个统一思路


【双端指针】


，但是双端指针的前提是对数据进行排序。OK！


STEP1 ->【排序】

接下来，【双端指针】控制的是两个指针，即两个变量。但题目要求是三数之和，因此这里明显的暗示我们要进行类比的转换。

这里我们这么考虑，在两数之和的题目中，我们感知到a+b = K，类比来看在三数之和里即a+b = K-c即可，即逻辑上我们将c从数组中排除，问题又回到了两数之和上。OK！


STEP2 ->【两数之和】

针对不重复这个要求，即当前参与运算的元素，和他后面相邻的元素不重复即可，如果重复略过即可 。这个去重既要针对c，也要针对a，b 。OK！


STEP3 ->【去重】

综上所述，代码如下：

public static void main(String[] args) {
        int [] source = {-1,0,1,2,-1,4};
        List<int []> result = getResult(source);
        for (int [] slice: result) {
            System.out.println("---");
            for (int value: slice) {
                System.out.println(value);
            }
        }
    }

    private static List<int[]> getResult(int[] source) {
        Arrays.sort(source);
        int idxFix = 0;
        List<int []> result = new ArrayList<>();
        while (idxFix<source.length-2){
            getTwoSum(idxFix,source,result);
            //对固定指针的一个去重处理，相邻元素相同则略过
            while (nums[fixIndex] == nums[fixIndex+1] && 
                              fixIndex < nums.length - 2){
                fixIndex++;
            }
            //向数组尾部移动指针
            idxFix = idxFix +1;
        }
        return result;
    }

    private static void getTwoSum(int idxFix, int[] source, List<int[]> result) {
        int idxStart = idxFix +1;
        int idxEnd = source.length-1;
        while (idxStart<idxEnd){
            if (source[idxStart]+source[idxEnd]+source[idxFix]==0){
                result.add(new int[]{source[idxStart],source[idxEnd],source[idxFix]});
                //对双端指针的一个去重处理，相邻元素相同则略过
                while (idxStart<source.length-1&&source[idxStart]==source[idxStart+1]){
                    idxStart++;
                }
                while (idxEnd<source.length-1&&source[idxEnd]==source[idxEnd-1]){
                    idxEnd--;
                }
                //从双端向内部逼近
                idxStart++;
                idxEnd--;
            }else if (source[idxStart]+source[idxEnd] + source[idxFix]<0){
                idxStart = idxStart + 1;
            }else {
                idxEnd = idxEnd -1;
            }
        }
    }