当前位置：首页 > news >正文

常见算法题目1 - 给定一个整数数组和一个目标值，找出数组中两个数之和等于目标值的数组下标组合

news 2025/5/23 5:17:04

算法题目1 - 给定一个整数数组和一个目标值，找出数组中两个数之和等于目标值的数组下标组合

1. 问题描述

给定一个整数数组nums和一个目标值target，找出数组中两个数之和等于目标值的数组下标组合。
例如：

int[] nums = {2, 6, 2, 4, 7};
int target = 8;
输出：
[0, 1]
[1, 2]

以下根据效率分享两种搜索算法。

2. 算法解决

2.1 暴力循环法

通过两层循环暴力枚举搜索，代码如下：

 /*** 题目：* 给定一个整数数组和一个目标值，找出数组中两个数之和等于目标值的索引* 暴力循环版 时间复杂度 O(n^2)* @param nums* @param target* @return*/private static List<int[]> twoSum1(int[] nums, int target) {List<int[]> result = new ArrayList<>();for (int i = 0;i < nums.length; i++) {for (int j = i + 1;j < nums.length; j++) {if (nums[i] + nums[j] == target) {result.add(new int[]{i, j});}}}return result;}

2.2 HashMap单层循环法

在单层循环中，借助map存储每一步循环的值及其数组索引下标，查找时直接检索map中是否包含对应元素，有的话直接获取索引下标，返回结果。相关代码如下：

  /*** 题目* 给定一个整数数组和一个目标值，找出数组中两个数之和等于目标值的索引* HashMap单层循环 时间复杂度 O(n)* @param nums* @param target* @return*/private static List<int[]> twoSum2(int[] nums, int target) {List<int[]> result = new ArrayList<>();// key为数值 value为数值对应的下标Map<Integer, List<Integer>> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {// 差值int subNum = target - nums[i];// 如果map中有对应匹配值 则记录结果if (map.containsKey(subNum)) {for (Integer index : map.get(subNum)) {result.add(new int[]{index, i});}}// 记录当前循环值map.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);}return result;}

3. 测试

调用测试：

public class TwoSumTest {public static void main(String[] args) {int[] nums = {2, 6, 2, 4, 7};int target = 8;List<int[]> list1 = twoSum1(nums, target);System.out.println("暴力循环结果：");for (int[] items : list1) {System.out.println(Arrays.toString(items));}System.out.println("-----------------------------");List<int[]> list2 = twoSum2(nums, target);System.out.println("HashMap单层循环结果：");for (int[] items : list2) {System.out.println(Arrays.toString(items));}}}