数组中的3个数之和为0

68 阅读 0 评论 45 点赞

我是靠谱客的博主拉长纸飞机，最近开发中收集的这篇文章主要介绍数组中的3个数之和为0，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

解题思路

从头到尾-2遍历数组，每次从中取出一个数num[i]，然后定义i+1,num.length-1两个指针，

当left<right时：循环

如果num[i]+num[left]+num[right]==0,则加入list中

如果小于0，则L++

如果大于0 ，则R--

直到结束

参考代码

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        //1.首先对数组进行排序
        //2.重头开始取出元素，然后定义两个指针
        
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();
        if(num==null||num.length<3){
            return new ArrayList<>();
        }
        
        Arrays.sort(num);
        for(int i=0;i<num.length-2;i++){
            int left=i+1;
            int right=num.length-1;
            //如果num[i]>0,则不可能存在三个数之和等于0
            if(num[i]>0){//因为已经排好序了，有一个正数说明以后都是正数
                break;
            }
            if(i>0 && num[i]==num[i-1]){
                continue;
            }
            while(left<right){
                int sum=num[left]+num[right]+num[i];
                if(sum==0){
                    ArrayList<Integer> list=new ArrayList<>();
                    list.add(num[i]);
                    list.add(num[left]);
                    list.add(num[right]);
                    res.add(list);
                    while(left<right && num[left]==num[left+1]){
                        left++;
                    }
                    while(left<right && num[right]==num[right-1]){
                        right--;
                    }
                    left++;
                    right--;
                }
                else if(sum>0){
                    right--;
                }
                else if(sum<0){
                    left++;
                }
            }
        }
        return res;
    }
}