ACM-ACM-ICPC算法示例之Hashing-题解.zip

import java.util.*; public class FourSum { static class Pair { int first, second; Pair(int first, int second) { this.first = first; this.second = second; } } /* * Returns a list containing 4 numbers present at different indexes which sum to target. If there are multiple solutions, * return any solution. * If there is no solution, return an empty list. */ static List<Integer> findSubset(int[] nums, int target) { List<Integer> result = new ArrayList<>(); // For every pair of elements, store their sum Map<Integer, Pair> map = new HashMap<>(); int n = nums.length; for (int i=0; i<n; i++) { for (int j=i+1; j<n; j++) { map.put(nums[i]+nums[j], new Pair(i, j)); } } for (int i=0; i<n; i++) { for (int j=i+1; j<n; j++) { int remainingSum = target - (nums[i] + nums[j]); if (map.containsKey(remainingSum)) { Pair pair = map.get(remainingSum); if (pair.first != i && pair.first != j && pair.second != i && pair.second != j) { result.addAll(Arrays.asList(nums[i], nums[j], nums[pair.first], nums[pair.second])); return result; } } } } return new ArrayList<Integer>(); } public static void main(String[] args) { int target = 23; int[] nums = {10, 2, 3, 4, 5, 9, 7, 8}; List<Integer> result = findSubset(nums, target); if (result.size() != 4) { System.out.println("Four elements with the given sum not found in the array!"); } else { for (int num : result) { System.out.print(num + " "); } System.out.println(); } } }