含重复值的Java 4-Sum算法失效问题排查

问题定义 #

给定一个包含n个整数的数组a[]，4-sum问题要求判断是否存在四个不同的索引i、j、k、l，使得a[i] + a[j] = a[k] + a[l]。

异常场景 #

测试数组{1, 2, 1, 2, 3, 4}时，未排序状态下传入fourSum方法能正确返回true；但对数组排序后（排序后数组为[1, 1, 2, 2, 3, 4]），方法返回false。实际上排序后的数组中存在满足条件的组合（比如索引0、3的和与索引1、2的和均为3），但算法未检测到。

调试输出 #

debug output
Original array: [1, 2, 1, 2, 3, 4]
Array for checking: [1, 1, 2, 2, 3, 4]
Checking: 2 vs 4 at indices 0, 1, 2, 3
Checking: 2 vs 5 at indices 0, 1, 2, 4
Checking: 2 vs 6 at indices 0, 1, 2, 5
Checking: 2 vs 5 at indices 0, 1, 3, 4
Checking: 2 vs 6 at indices 0, 1, 3, 5
Checking: 2 vs 7 at indices 0, 1, 4, 5
Checking: 3 vs 5 at indices 0, 2, 3, 4
Checking: 3 vs 6 at indices 0, 2, 3, 5
Checking: 3 vs 7 at indices 0, 2, 4, 5
Checking: 3 vs 7 at indices 0, 3, 4, 5

已尝试方案 #

• 先对数组排序以分组重复值
• 计划在循环中跳过重复项以避免冗余检查（暂未在代码中实现）

待解问题 #

• 为何该算法无法找到正确的4-Sum组合？
• 处理重复值时是否遗漏了某个逻辑步骤？

代码实现 #

import java.util.Arrays;

public class FourSum {

    public static boolean fourSum(int[] a) {
        int n = a.length;
        if (n < 4) {
            return false;
        }
        
     //   Arrays.sort(a);
        System.out.println("Array for checking: " + Arrays.toString(a));
        
        for (int i = 0; i < n - 3; i++) {
            for (int j = i + 1; j < n - 2; j++) {
                for (int k = j + 1; k < n - 1; k++) {
                    for (int l = k + 1; l < n; l++) {
                        int sum1 = a[i] + a[j];
                        int sum2 = a[k] + a[l];
                        
                        // Debug print for every check
                        System.out.println("Checking: " + sum1 + " vs " + sum2 + " at indices " + i + ", " + j + ", " + k + ", " + l);
                        
                        // Specific check for our known solution
                        if (i == 0 && j == 2 && k == 1 && l == 3) {
                            System.out.println("KNOWN SOLUTION CHECK: " + sum1 + " vs " + sum2);
                        }
                        
                        if (sum1 == sum2) {
                            System.out.println("Found 4-SUM: " + a[i] + " + " + a[j] + " = " + a[k] + " + " + a[l] + " at indices " + i + ", " + j + ", " + k + ", " + l);
                            return true;
                        }
                    }
                }
            }
        }
        
        return false;
    }

    public static void main(String[] args) {
        int[] array = {1, 2, 1, 2, 3, 4};  // Example where 4-SUM condition should be met
        System.out.println("Original array: " + Arrays.toString(array));
        
        Arrays.sort(array);
        boolean resultSorted = fourSum(array);
        System.out.println("Result with sorting: " + resultSorted);
    }
}

内容的提问来源于Stack Exchange，提问作者Anthony Pate