@Test(timeout = 1000) public void performanceTest() { long time1 = 0, time2 = 0; int N = 1000; int[] a = getRandomArray(N, 1, N * N); long st = System.nanoTime(); Assert.assertEquals(false, FourSum.solveInN2(a)); time1 = System.nanoTime() - st; N <<= 1; a = getRandomArray(N, 1, N * N); st = System.nanoTime(); Assert.assertEquals(false, FourSum.solveInN2(a)); time2 = System.nanoTime() - st; System.out.println(time1 + "," + time2); }
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);  }