1.4.14 4-sum。为4-sum设计一个算法。

写到最前: 后续会减少直接贴 GPT 图.

为了便于后续的阅读者和我自己, 方便地直接使用或编辑 GPT 相关的描述, 后续将以引用方式备注出来来自 GPT 的文案或者代码. 直接贴图看着更直观, 但是真到需要用时, 会很尴尬.

我的初版答案, 时间复杂度 O(N^3 * logN)

public class FourSumFast {
    public static int count(int[] a) {
        Arrays.sort(a);
        int N = a.length;
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                for (int k = j + 1; k < N; k++) {
                    if (BinarySearch.rank(-a[i] - a[j] - a[k], a) > k) {
                        cnt++;
                    }
                }
            }
        }
        return cnt;
    }
}

思路,相对很简单, 就是把最内层,由循环改成二分查找.如果用四重循环的话, 时间复杂度, 会变成 O(N^4).

给定的用例数据的实行时间如下:

         * 1Kints time:3.565 s;count: 13654
         * 2Kints time:34.223 s;count: 220115

GPT4 的答案, 基于双指针, 时间复杂度 O(N^3)

public class FourSumFastGPT {
    public static int count(int[] nums) {
        int target = 0;

        int count = 0;
        int n = nums.length;

        if (nums == null || n < 4)
            return count;

        Arrays.sort(nums);

        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) // Prevents duplicate results
                continue;
            if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) // min > target
                break;

            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) // Prevents duplicate results
                    continue;

                int left = j + 1, right = n - 1;
                while (left < right) {
                    int sum = nums[i] + nums[j] + 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;
    }
}

这个方法, 我确实没想到. 双指针法, 最坏情况下的时间复杂度为 O(N), 再加上两层循环, 所以就是 O(N^3).

下面是 GPT4的解题思路:

算法思想

对于四数之和的问题，一个有效的解决方案是固定两个数，然后使用双指针对剩下的两个数进行处理. 为了使问题更简单，首先对数组进行排序.

此外，考虑到算法需要找出所有满足条件的四元组, 而不仅仅是计算有多少个这样的四元组，所以需要避免重复。

步骤

  1. 对数组 a[] 进行排序。

  2. 用两个嵌套循环在 a[] 中固定两个元素 a[i] 和 a[j]。

  3. 在 i+1 和 j-1 之间用两个指针 k 和 m寻找满足 a[i] + a[j] + a[k] + a[m] = 0 的元素对。

    • 如果总和大于0，那么 m--。

    • 如果总和小于0，那么 k++。

    • 如果总和等于0，那么这四个元素就是一个解。

  4. 跳过所有重复的元素对，以避免重复的结果。

浅思: 这是第二次碰到 双指针法

需要适当 双指针法. 目前看, 抽象方法, 主要是将对数组的操作, 转换为对指针的操作. 配合对数据进行排序, 可以兼容一些冗余的非必要操作, 如: 不用反复地来回遍历数组.

参考: