程序设计－寻找三数之和为零的三元组（Java）

全栈程序员-站长 • 2022年6月21日下午6:46 • 未分类 • 阅读 22

大家好，又见面了，我是你们的朋友全栈君。

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击http://www.captainbed.net

package live.every.day.Programming;

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

/**
 * 给定一个包含n个整数的数组nums，判断nums中是否存在三个元素a、b、c，使得a+b+c=0。
 * 找出所有满足条件且不重复的三元组。
 *
 * @author Created by LiveEveryDay
 */
public class ThreeNumbersSumEqualsZero {

    public static ArrayList<ArrayList<Integer>> solve(int[] nums) {

        // 三元组用ArrayList<Integer>来表示
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();

        if (nums == null || nums.length == 0) {
            return result;
        }

        // 排序
        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 2; i++) {

            // 避免计算重复元素
            if (i != 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            /**
             * 固定一个数，从后面的数中选出两个数。
             * 因为数组是有序的，所以可以用两个数组下标left和right，left指向当前元素的后一个位置，right指向数组的最后一个位置。
             * 三数相加的和等于0时，加入解集；
             * 三数相加的和小于0时，把left往右边移动；
             * 三数相加的和大于0时，把right往左边移动。
             */
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    ArrayList<Integer> r = new ArrayList<>();
                    r.add(nums[i]);
                    r.add(nums[left]);
                    r.add(nums[right]);
                    result.add(r);
                    left++;
                    right--;

                    // 避免计算重复元素
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }

                    // 避免计算重复元素
                    while (left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return result;
    }

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

        int[] nums2 = {0};
        System.out.println(solve(nums2));

        int[] nums3 = {1, 2, 3, 4, 5, 6};
        System.out.println(solve(nums3));
    }

}

// Output:
/*
[[-1, -1, 2], [-1, 0, 1]]
[]
[]
*/

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/151780.html原文链接：https://javaforall.net