Java中如何实现三数之和

在算法和数据结构的学习中，”三数之和”是一个经典的问题。给定一个包含n个整数的数组，要求找出所有满足三个数之和等于目标值的组合。本文将介绍如何在Java中实现这一算法。

问题描述

给定一个整数数组nums和一个目标值target，找出数组中所有满足nums[i] + nums[j] + nums[k] = target的三元组(i, j, k)，其中i, j, k是数组中的不同索引。

解决思路

1. 暴力解法

最直观的解法是使用三重循环遍历所有可能的三元组，检查它们的和是否等于目标值。这种方法的时间复杂度为O(n^3)，在数组较大时效率较低。

public List<List<Integer>> threeSum(int[] nums, int target) {
    List<List<Integer>> result = new ArrayList<>();
    for (int i = 0; i < nums.length - 2; i++) {
        for (int j = i + 1; j < nums.length - 1; j++) {
            for (int k = j + 1; k < nums.length; k++) {
                if (nums[i] + nums[j] + nums[k] == target) {
                    result.add(Arrays.asList(nums[i], nums[j], nums[k]));
                }
            }
        }
    }
    return result;
}

2. 排序加双指针

为了提高效率，我们可以先对数组进行排序，然后使用双指针的方法来减少时间复杂度。具体步骤如下：

1. 对数组进行排序。
2. 遍历数组，固定一个数nums[i]，然后使用双指针left和right分别指向i+1和n-1。
3. 计算nums[i] + nums[left] + nums[right]的和：
   • 如果和等于目标值，将三元组加入结果集，并移动指针left和right。
   • 如果和小于目标值，移动left指针。
   • 如果和大于目标值，移动right指针。
4. 重复上述步骤直到遍历完整个数组。

这种方法的时间复杂度为O(n^2)，效率较高。

public List<List<Integer>> threeSum(int[] nums, int target) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue; // 跳过重复元素
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == target) {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                while (left < right && nums[left] == nums[left + 1]) left++; // 跳过重复元素
                while (left < right && nums[right] == nums[right - 1]) right--; // 跳过重复元素
                left++;
                right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
}

总结

通过排序和双指针的方法，我们可以有效地解决三数之和的问题。这种方法不仅减少了时间复杂度，还避免了重复的三元组。在实际应用中，这种算法可以用于解决类似的问题，如四数之和、最接近的三数之和等。

希望本文对你理解如何在Java中实现三数之和有所帮助。如果你有任何问题或建议，欢迎在评论区留言讨论。