寻找和为指定值的唯一四元组：内存超限问题求助

DevOps 小满

2026-8-21

寻找和为指定值的唯一四元组：内存超限优化方案

我需要完成寻找和为指定值的唯一四元组任务，输入是包含n个可重复元素的数组data与目标和s。当前实现采用双重循环（i∈[0,n-1]，j∈[i+1,n]），将唯一元素对存入Map（键为元素对和，值为对应元素对集合），循环内执行以下步骤：

检查Map中是否存在s与当前元素对和的差值；
若存在，验证当前元素对与已存元素对索引不重叠，符合条件则加入结果集；
将当前元素对存入Map。

该实现触发内存超限，要求时间复杂度保持O(n²)，Pair和Forths仅含基本类型字段，求优化方案。

原实现代码

SunForthFAIL类

public class SunForthFAIL {

  public static void main(String[] args) throws IOException {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(reader.readLine());
    int s = Integer.parseInt(reader.readLine());
    int[] data = new int[n];
    Set<Forths> result = new HashSet<>();
    Map<Integer, Set<Pair>> history = new HashMap<>();

    StringTokenizer stringTokenizer = new StringTokenizer(reader.readLine());
    for (int i = 0; i < n; i++) {
      data[i] = Integer.parseInt(stringTokenizer.nextToken());
    }
    Arrays.sort(data);

    for (int i = 0; i < n - 1; i++) {
      for (int j = i + 1; j < n; j++) {

        int sum = data[i] + data[j];
        int target = s - sum;
        if (history.containsKey(target)) {
          for (Pair historyPair : history.get(target)) {
            if (historyPair.isDiff(i, j)) {
              result.add(new Forths(historyPair.getiValue(), historyPair.getjValue(), data[i], data[j]));
            }
          }

        }


        if (history.containsKey(sum)) {
          history.get(sum).add(new Pair(i, j, data[i], data[j]));
        } else {
          Set<Pair> set = new HashSet<>();
          set.add(new Pair(i, j, data[i], data[j]));
          history.put(data[i] + data[j], set);
        }

      }
    }
    System.out.println(result.size());
    result.stream().sorted(Comparator.comparingInt(Forths::getFirst).thenComparing(Comparator.comparingInt(Forths::getSecond))).forEach(x -> System.out.println(x));
  }
}

Pair类

class Pair {

  private int i;
  private int j;
  private int iValue;
  private int jValue;

  public int getiValue() {
    return iValue;
  }

  public int getjValue() {
    return jValue;
  }

  public Pair(int i, int j, int iValue, int jValue) {
    this.i = i;
    this.j = j;
    this.iValue = iValue;
    this.jValue = jValue;
    ;
  }

  public boolean isEquel(int i, int j) {
    if (Math.min(iValue, jValue) == Math.min(i, j) &&
            Math.max(iValue, jValue) == Math.max(i, j))
      return true;
    else
      return false;
  }

  @Override
  public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    Pair pair = (Pair) o;
    if (Math.min(iValue, jValue) == Math.min(pair.iValue, pair.jValue) &&
            Math.max(iValue, jValue) == Math.max(pair.iValue, pair.jValue))
      return true;
    else
      return false;
  }

  @Override
  public int hashCode() {
    return Objects.hash(Math.min(iValue, jValue) + " " + Math.max(iValue, jValue));
  }

  public boolean isDiff(int i, int j) {
    if (this.i == i || this.i == j || this.j == i || this.j == j)
      return false;
    else
      return true;
  }
}

Forths类

class Forths {

  private int first;
  private int second;
  private int third;
  private int forth;


  public int getFirst() {
    return first;
  }

  public int getSecond() {
    return second;
  }


  public Forths(int a, int b, int c, int d) {
    int[] arr = new int[]{a, b, c, d};
    Arrays.sort(arr);
    this.first = arr[0];
    this.second = arr[1];
    this.third = arr[2];
    this.forth = arr[3];

  }

  @Override
  public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    Forths forths = (Forths) o;
    return first == forths.first && second == forths.second && third == forths.third && forth == forths.forth;
  }

  @Override
  public int hashCode() {
    return Objects.hash(first, second, third, forth);
  }

  @Override
  public String toString() {
    return first + " " + second + " " + third + " " + forth;
  }
}

优化方案

1. 替换Map存储逻辑，改用双指针法（核心优化）

原方案中Map存储了O(n²)级别的元素对，是内存超限的核心原因。利用数组已排序的特性，改用双重循环+双指针的思路，完全避免大规模存储元素对：

外层循环固定前两个元素的索引i和j（i < j）；
用双指针left = j+1、right = n-1在剩余元素中寻找和为s - data[i] - data[j]的两个元素；
过程中跳过重复元素，直接生成唯一四元组。

该方案时间复杂度仍为O(n²)，内存仅需存储结果集，内存占用大幅降低。示例代码如下：

public class SunForthOpt {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        int s = Integer.parseInt(reader.readLine());
        int[] data = new int[n];
        Set<Forths> result = new HashSet<>();

        StringTokenizer stringTokenizer = new StringTokenizer(reader.readLine());
        for (int i = 0; i < n; i++) {
            data[i] = Integer.parseInt(stringTokenizer.nextToken());
        }
        Arrays.sort(data);

        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && data[i] == data[i-1]) continue; // 跳过重复的第一个元素
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && data[j] == data[j-1]) continue; // 跳过重复的第二个元素
                int left = j + 1;
                int right = n - 1;
                int target = s - data[i] - data[j];
                while (left < right) {
                    int sum = data[left] + data[right];
                    if (sum == target) {
                        result.add(new Forths(data[i], data[j], data[left], data[right]));
                        // 跳过重复的左指针元素
                        while (left < right && data[left] == data[left+1]) left++;
                        // 跳过重复的右指针元素
                        while (left < right && data[right] == data[right-1]) right--;
                        left++;
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }

        System.out.println(result.size());
        result.stream().sorted(Comparator.comparingInt(Forths::getFirst).thenComparing(Comparator.comparingInt(Forths::getSecond))).forEach(System.out::println);
    }
}

2. 精简Pair类（若仍需保留Map方案）

如果必须保留原Map思路，可大幅精简Pair类：

去掉索引字段，仅存储元素对的值（数组已排序，可保证val1 <= val2）；
优化equals和hashCode实现，避免字符串拼接操作，直接基于两个值计算哈希。

示例精简Pair类：

class Pair {
    private final int val1;
    private final int val2;

    public Pair(int val1, int val2) {
        this.val1 = Math.min(val1, val2);
        this.val2 = Math.max(val1, val2);
    }

    public int getVal1() {
        return val1;
    }

    public int getVal2() {
        return val2;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Pair pair = (Pair) o;
        return val1 == pair.val1 && val2 == pair.val2;
    }

    @Override
    public int hashCode() {
        return Objects.hash(val1, val2);
    }
}

3. 提前去重，减少无效对象创建

在双重循环中提前跳过重复元素，避免生成大量重复的元素对和四元组：

当i > 0且data[i] == data[i-1]时，跳过当前i；
当j > i+1且data[j] == data[j-1]时，跳过当前j。

内容的提问来源于stack exchange，提问作者Gosha Efimenko

寻找和为指定值的唯一四元组：内存超限问题求助

原实现代码 #

SunForthFAIL类 #

Pair类 #

Forths类 #

优化方案 #

1. 替换Map存储逻辑，改用双指针法（核心优化） #

2. 精简Pair类（若仍需保留Map方案） #

3. 提前去重，减少无效对象创建 #