首页 > 代码库 > CC150 19.11
CC150 19.11
19.11 Design an algorithm to find all pairs of integers within an array which sum to a specified value.
// Assume a is not null. // // a is not sorted. // // Option 1 is using a set. List<Pair<Integer, Integer>> sumUpTo(int[] a, int sum) { // Option 1 Map<Integer> set = new HashSet<>(); List<Pair<Integer, Integer>> toReturn = new ArrayList<>(); for (int i : a) { if (set.contains(i)) { toReturn.add(Pair.of(i , sum - i)); } else { set.add(sum - i); } } return toReturn; // Option 2 // Not use a set, but use a bit map. BitSet bs = new BitSet(); for (int i : a) { if (bs.get(i)) toReturn.add(Pair.of(i , sum - i)); else bs.set(sum - i); } return toReturn; // Option 3 // Sort first, and iterate from both beginning and end. List<Pair<Integer, Integer>> toReturn = new ArrayList<>(); int[] sorted = sortAsc(a); int l = 0; int r = sorted.length - 1; while (l < r) { if (a[l] + a[r] < sum) { l ++; } else if (a[l] + a[r] > sum) { r --; } else // == { toReturn.add(Pair.Of(a[l], a[r])); l ++; r --; } } return toReturn; }
CC150 19.11
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。