查找数组中3个相加和为零的元素_sums数组中找出三个一元组加起来为0

输入 : arr[] = {0, -1, 2, -3, 1}
输出: 0 -1 1
         2 -3 1

输入: arr[] = {1, -2, 1, 0, 5}
输出: 1 -2  1
1
2
3
4
5
6

解法1（简单时间复杂复杂度O（n^3）空间复杂度O（1））

public static  void findTriplets(int arr[], int n){
        for(int i=0;i<n-2;i++)
            for(int j=i+1;j<n-1;j++)
                for(int k=j+1;j<n;j++)
                {
                //使用三重循环取到数组中的任意三个值相加，如果为0则输出
                    if(arr[i]+arr[j]+arr[k]==0)
                     System.out.println(arr[i]+" "+arr[j]+" "+arr[k]);
                }


    }
1
2
3
4
5
6
7
8
9
10
11
12

解法2（时间复杂度O（n^2）空间复杂度O（1））

算法思想：
现将数组排序，i 指向数组的开始，j 指向i 的后一位，k 指向数组最后，如果
arr[i]+arr[j]+arr[k]==0，j++,k–;
否则如果
arr[i]+arr[j]+arr[k]>0
k–;
否则
arr[i]+arr[j]+arr[k]<0
i++;

public static  void findTriplets(int arr[], int n){
        Arrays.sort(arr);//把数组先从小到大排序
        for(int i=0;i<n-2;i++)
        {
            int j=i+1;
            int k=n-1;
            while(k>j)
            {
                if(arr[i]+arr[j]+arr[k]==0)
                {//如果相加为0就输出
                    System.out.println(arr[i]+" "+arr[j]+" "+arr[k]);
                    j++;
                    k--;
                }
                else if(arr[i]+arr[j]+arr[k]>0){
                    k--;
                    //如果相加大于0时k--
                }
                else {
                    j++;
                    //相加小于0时j++
                }
            }


        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28