Given an array A of integers, find the index of values that satisfy A + B = C + D, where A,B,C & D are integers values in the array
Note:
1) Return the indices `A1 B1 C1 D1`, so that
A[A1] + A[B1] = A[C1] + A[D1]
A1 < B1, C1 < D1
A1 < C1, B1 != D1, B1 != C1
2) If there are more than one solutions,
then return the tuple of values which are lexicographical smallest.
Assume we have two solutions
S1 : A1 B1 C1 D1 ( these are values of indices int the array )
S2 : A2 B2 C2 D2
S1 is lexicographically smaller than S2 iff
A1 < A2 OR
A1 = A2 AND B1 < B2 OR
A1 = A2 AND B1 = B2 AND C1 < C2 OR
A1 = A2 AND B1 = B2 AND C1 = C2 AND D1 < D2
public class Solution { static class Pair { int x; int y;
public Pair(int x, int y) { this.x = x; this.y = y; } }
public int compare(ArrayList<Integer> A, ArrayList<Integer> B) { for (int i = 0; i < A.size(); i ++) { int a = A.get(i); int b = B.get(i); if (a < b) { return -1; } else if (a > b) { return 1; } } return 0; }
public ArrayList<Integer> equal(ArrayList<Integer> A) { ArrayList<Integer> result = new ArrayList<>(); Map<Integer, Pair> map = new HashMap<>(); for (int j = 1; j < A.size(); j ++) { for (int i = 0; i < j; i ++) { int sum = A.get(i) + A.get(j); if (map.containsKey(sum) && map.get(sum).x < i && map.get(sum).y != i && map.get(sum).y != j) { Pair p = map.get(sum); ArrayList<Integer> candidate = new ArrayList<>(); candidate.add(p.x); candidate.add(p.y); candidate.add(i); candidate.add(j); if (result.isEmpty()) { result = candidate; } else if (compare(candidate, result) < 0) { result = candidate; } } if (!map.containsKey(sum)) { map.put(sum, new Pair(i, j)); } } } return result; } }