搜索唯一的四位数以获取定义的总和

Question

我的任务是找到四个唯一元素，其总和已定义。所以我有输入数据：n个元素的数据数组，元素可以重复，'s'是总和。我有两个循环，第一个 i 在值 [0, n-1] 中，第二个 j 在 [i+1, n] 中。我保存在 Map 中的所有唯一元素对，其中键是总和，值是由该总和组成的可能元素的集合。结果是输入数据数组的四个唯一元素的集合。我在第二个周期中执行的所有操作：

1. 我检查 's' 和 data[i]+data[j] 之间是否已经有不同，2）如果有，我检查 data[i] 和 data[j] 是否与保存对中的元素不重合并添加到结果中。
2. 将这对 data[i] + data [ j] 添加到具有历史记录的 Map

我在这项任务中遇到了内存限制，但我克服了它。时间限制为 O(n^2)。据我了解，我做了一些额外的操作并保存了一些不必要的数据。我创建了两个对象 Fourths 和 Pairs ，但它们内部只有原始字段，所以我认为其中没有什么交易

这是我的java代码：

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));
  }
}

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;
  }
}

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;
  }
}

Answer 1

就我而言，我将 Pair 对象更改为int[2]，并带有对元素的索引。并且内存限制问题已解决。