1.4.15 快速3-sum。作为热身，使用一个线性级别的算法(而非基于二分查找的线性对数级别的算法)实现TwoSumFaster来计算已排序的数组中和为0的整数对的数量。用相同的思想为3-sum问题给出一个平方级别的算法。

我的初版答案: 基于1.4.14 GPT4的双指针解法, 快速改了下.

public class TwoSumFast1415 {
    public static int count(int[] nums) {
        Arrays.sort(nums);
        int N = nums.length;
        int count = 0;
        int target = 0;

        int left = 0, right = N - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                count++;
                while (left < right && nums[left] == nums[left + 1])
                    left++; // Prevents duplications
                while (right > left && nums[right] == nums[right - 1])
                    right--; // Prevents duplications
                left++;
                right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }

        return count;
    }
}

public class ThreeSumFast1415 {
    public static int count(int[] nums) {
        Arrays.sort(nums);
        int N = nums.length;
        int target = 0;
        int count = 0;
        for (int i = 0; i < N - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) // Prevents duplicate results
                continue;
            if (nums[i] + nums[i + 1] + nums[i + 2] > target) // min > target
                break;

            int left = i + 1, right = N - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == target) {
                    count++;
                    while (left < right && nums[left] == nums[left + 1])
                        left++; // Prevents duplications
                    while (right > left && nums[right] == nums[right - 1])
                        right--; // Prevents duplications
                    left++;
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return count;
    }
}

问问GPT4

问: 是否符合题目要求?

这两段代码均满足了题目要求：

  1. TwoSumFast1415 类中的 count 函数：
    • 此函数采用了线性时间复杂度的算法（而非二分查找），这是通过使用两个指针（一个从起始位置开始，另一个从末尾开始，共同向中心移动）实现的。
    • 先排序数组，然后遍历数组，将和等于0的不重复整数对计数并返回。
  2. ThreeSumFast1415 类中的 count 函数：
    • 使用的是平方级别的算法。在外层有一个用于遍历每一个数的循环；在内层，使用了类似于 TwoSumFast 中的双指针方法，对每一次外层循环找出目标的和等于0的对。
    • 它也避免计算重复的整数对，并在确定最小可能和大于目标时提前结束。

所以，以上代码完全符合题目的要求，良好的完成了任务。

问: 从算法实现角度, 有无可能进一步优化, 让运行效率更快?

两个算法已经非常有效率，对于 TwoSumFast 的实现，其时间复杂度已经达到最优 —— O(n)。对于 ThreeSumFast，其时间复杂度为 O(n^2)，这在没有更多信息可以用来减小搜索空间的情况下，也是最优的。

补充: 贴下 ThreeSum 各个版本的代码的执行时间.

/*
    * ThreeSum:
    * 1Kints time:0.082 s;count: 70
    * 2Kints time:0.5 s;count: 528
    * 4Kints time:2.07 s;count: 4039
    * 8Kints time:16.147 s;count: 32074
    * 
    * ThreeSumFast:
    * 1Kints time:0.033 s;count: 70
    * 2Kints time:0.062 s;count: 528
    * 4Kints time:0.26 s;count: 4039
    * 8Kints time:1.146 s;count: 32074
    * 
    * ThreeSumFast1415:
    * 1Kints time:0.015 s;count: 70
    * 2Kints time:0.009 s;count: 528
    * 4Kints time:0.022 s;count: 4039
    * 8Kints time:0.08 s;count: 32074
    */