Search unique fours for the defined sum

Question

I have a task to find four unique elements , sum of which is defined. So I have as input data : data array of n elemeents, elements can be duplicated, and 's' is sum. I have two cycles , first i in values [0, n-1], second j in [i+1, n]. All unique pairs of elements I save in Map , where key is sum and value is Collections of possible elements whats consists that sum. Result is collection of four unique elements of input data array. All actions I do in second cycle :

1. I check if I already have a differents beetween 's' and data[i]+data[j] , 2)if I have I check , if data[i] and data[j] doesn't coinside with elements from saved pairs and add to reslut.
2. Add this pair data[i] + data [ j] to Map with history

I have a Memory Limit in this task and I get over it. Time limit is O(n^2). As I undestand I do some extra actions and save some unnecessary data.I created two object Fourths and Pairs , but they has only primitive fields inside so I thinK what deal is not in that

Here is my code in 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

In my case, I change the Pair object to int[2], with indexes of pair elements. And memory limit issue is resolved.