@Test public void correctTest() { int idx = 0; for (int i = 0; i < 10; i++) { Set<Boolean> s = new HashSet<>(); int k = 1000; while (s.size() < 2) { int N = r.nextInt(k); int[] a = getRandomArray(N, -k * k, k * k); boolean res = FourSum.solveInN2(a); s.add(res); Assert.assertEquals(expect(a), res); idx++; } } System.out.println("test " + idx); }
public static boolean solveInN2(int[] a) { Map<Integer, Pair> map = new HashMap<>(); for (int i = 0; i < a.length; i++) { for (int j = i + 1; j < a.length; j++) { int need = -a[i] - a[j]; Pair cur = new Pair(i, j); if (map.containsKey(need)) { if (map.get(need).noIntersect(cur)) { return true; } } map.putIfAbsent(-need, cur); } } return false; }
FourSum { public static boolean solveInN2(int[] a) { Map<Integer, Pair> map = new HashMap<>(); for (int i = 0; i < a.length; i++) { for (int j = i + 1; j < a.length; j++) { int need = -a[i] - a[j]; Pair cur = new Pair(i, j); if (map.containsKey(need)) { if (map.get(need).noIntersect(cur)) { return true; } } map.putIfAbsent(-need, cur); } } return false; } }
FourSum { public static boolean solveInN2(int[] a) { Map<Integer, Pair> map = new HashMap<>(); for (int i = 0; i < a.length; i++) { for (int j = i + 1; j < a.length; j++) { int need = -a[i] - a[j]; Pair cur = new Pair(i, j); if (map.containsKey(need)) { if (map.get(need).noIntersect(cur)) { return true; } } map.putIfAbsent(-need, cur); } } return false; }  }
FourSum { public static boolean solveInN2(int[] a) { Map<Integer, Pair> map = new HashMap<>(); for (int i = 0; i < a.length; i++) { for (int j = i + 1; j < a.length; j++) { int need = -a[i] - a[j]; Pair cur = new Pair(i, j); if (map.containsKey(need)) { if (map.get(need).noIntersect(cur)) { return true; } } map.putIfAbsent(-need, cur); } } return false; }  static boolean solveInN2(int[] a); }
FourSum { public static boolean solveInN2(int[] a) { Map<Integer, Pair> map = new HashMap<>(); for (int i = 0; i < a.length; i++) { for (int j = i + 1; j < a.length; j++) { int need = -a[i] - a[j]; Pair cur = new Pair(i, j); if (map.containsKey(need)) { if (map.get(need).noIntersect(cur)) { return true; } } map.putIfAbsent(-need, cur); } } return false; }  static boolean solveInN2(int[] a);  }