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();
}
}
}
ACM-ACM竞赛常用算法之哈希算法实现.zip
需积分: 1 171 浏览量
2024-03-09
20:12:54
上传
评论
收藏 6KB ZIP 举报
DdddJMs__135
- 粉丝: 715
- 资源: 216
最新资源
- 论文(最终)_20240430235101.pdf
- 基于python编写的Keras深度学习框架开发,利用卷积神经网络CNN,快速识别图片并进行分类
- 最全空间计量实证方法(空间杜宾模型和检验以及结果解释文档).txt
- 5uonly.apk
- 蓝桥杯Python组的历年真题
- 2023-04-06-项目笔记 - 第一百十九阶段 - 4.4.2.117全局变量的作用域-117 -2024.04.30
- 2023-04-06-项目笔记 - 第一百十九阶段 - 4.4.2.117全局变量的作用域-117 -2024.04.30
- 前端开发技术实验报告:内含4四实验&实验报告
- Highlight Plus v20.0.1
- 林周瑜-论文.docx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈