- Find all pairs of elements in a given array that sum to the pair the given target number. Return all the distinct pairs of values.
- Assumptions
- The given array is not null and has length of at least 2
- The order of the values in the pair does not matter
- Examples
- A = {2, 1, 3, 2, 4, 3, 4, 2}, target = 6, return [[2, 4], [3, 3]]
- Time: O(N)
- public class Solution {
- public List<List<Integer>> allPairs(int[] array, int target) {
- // Write your solution here
- List<List<Integer>> res = new ArrayList<>();
- Map<Integer, Integer> map = new HashMap<>();
- for (int num : array) {
- Integer freq = map.get(num);
- int other = target - num;
- if (other != num && map.containsKey(other) && freq == null) {
- res.add(Arrays.asList(other, num));
- } else if (num + num == target && freq != null && freq == 1) {
- res.add(Arrays.asList(num, num));
- }
- if (freq == null) {
- map.put(num, 1);
- } else {
- map.put(num, freq + 1);
- }
- }
- return res;
- }
- }
- Time: O(NlogN)
- public class Solution {
- /**
- * @param nums: an array of integer
- * @param target: An integer
- * @return: An integer
- */
- public int twoSum6(int[] array, int target) {
- // write your code here
- if (array == null || array.length <= 1) {
- return 0;
- }
- Arrays.sort(array);
- int res = 0;
- int left = 0, right = array.length - 1;
- while (left < right) {
- int tmpSum = array[left] + array[right];
- if (tmpSum == target) {
- res += 1;
- left += 1;
- while (left <= right && array[left] == array[left - 1]) {
- left += 1;
- }
- } else if (tmpSum < target) {
- left += 1;
- } else {
- right -= 1;
- }
- }
- return res;
- }
- }
- [Algo] 182. 2 Sum All Pair II
来源: http://www.bubuko.com/infodetail-3446449.html