三数之和，求三个数之和为0（双指针法）

127 阅读 0 评论 84 点赞

我是靠谱客的博主强健中心，最近开发中收集的这篇文章主要介绍三数之和，求三个数之和为0（双指针法），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

第一步需要定义数组数据和main方法

  public static void main(String[] args) {
        int[] input = {-1, 0, 1, 2, -1, -4};
        ThreeFem threeFem = new ThreeFem();
        System.out.println(threeFem.threeFem(input));
    }

第二步定义数组长度和排序

  int n = nums.length;
        List<List<Integer>> result = new ArrayList<>();
        //先对数组排序（nlogn复杂度）
        Arrays.sort(nums);

循环遍历数组，我们筛选三元数组中最小的值作为i指针，固定 3 个指针中最左（最小）数字的指针 i，双指针 L，R 分设在数组索引 (i, len(nums)) 两端，所以初始值，i=0；L=i+1；R=nums.length-1；

 //定义指针
            int lp = i + 1;
            int rp = n - 1;

接下来需要先考虑特殊情况了。

1.1如果当前的i指针指向的数已经大于0了，直接退出循环

for (int i = 0; i < n; i++) {
            //1.1首选处理特殊情况，如果当前数已经大于0，直接退出循环
            if (nums[i] > 0) {
                break;
            }
....

1.2我愿称之为去重

  //1.2如果当前数据已经出现过，直接跳过
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

1.3接下来就是判断是左右指针移动问题，只要左右指针不重叠，就继续移动；

循环计算当前三数之和：

sum = nums[i] + nums[L] + nums[R]

并按照以下规则执行双指针移动：

当sum < 0时，L ++并跳过所有重复的nums[L]；
由于sum<0，L一直右移，直到跟R重合。如果依然没有结果，那么i++，换下一个数考虑
初始同样还是L=i+1，R=nums.length-1。同样，继续判断sum。
找到一组解之后，继续移动L和R，判断sum，如果小于0就右移L，如果大于0就左移R：

如果L和R相遇或者L>R，代表当前i已经排查完毕，i++；如果i指向的数跟i-1一样，那么直接继续i++，考察下一个数；整体代码如下

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class ThreeFem {
    public static void main(String[] args) {
        int[] input = {-1, 0, 1, 2, -1, -4};
        ThreeFem threeFem = new ThreeFem();
        System.out.println(threeFem.threeFem(input));
    }


    public List<List<Integer>> threeFem(int[] nums) {
        int n = nums.length;
        List<List<Integer>> result = new ArrayList<>();
        //数组排序
        Arrays.sort(nums);
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                break;
            }
            //去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            //定义指针
            int lp = i + 1;
            int rp = n - 1;
            while (lp < rp) {
                int sum  = nums[i] + nums[lp] + nums[rp];
                if(sum == 0 ){
                    result.add(Arrays.asList(nums[i],nums[lp],nums[rp]));
                    lp ++;
                    rp --;
                    //去重
                    while (lp < rp && nums[lp] == nums[lp - 1]){
                        lp++;
                    }
                    while (lp < rp && nums[rp] == nums[rp +1]) {
                        rp--;

                    }


                }else if(sum < 0 ){
                    lp++;
                }else {
                    rp--;
                }

            }
        }


        return result;
    }
}