算法练习01

一、题目

给定一个整数数组 nums 和一个整数目标值target，请你在该数组 中找出 和为目标值 target 的那 两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。 你可以按任意顺序返回答案。

• 示例 1: 输入:nums =[2,7,11,15]，target = 9 输出:[0，1] 解释:因为nums[0]+nums[1]==9，返回[0，1]。
• 示例 2: 输入:nums=[3,2,4]，target =6 输出:[1，2]
• 示例 3: 输入:nums=[3,3]，target =6 输出:[0，1]

 提示: 2<= nums.length <= 10 。-109 <= nums[i]<= 109 -109 <= target <= 109 。

二、实现思路

1.哈希表：使用一个哈希表（HashMap）来存储数组中已经访问过的元素及其对应的下标。
2.遍历数组：对于每个元素，计算目标值与当前元素的差值。
3.查找哈希表：检查差值是否在哈希表中存在。
4.如果存在，说明找到了两个数，它们的和为目标值，返回它们的下标。
5.如果不存在，将当前元素及其下标存入哈希表中。
6.返回结果：如果遍历结束后没有找到符合条件的两个数，则返回空数组（根据题意，这种情况不会发生）。

三、代码实现

package com.thor.test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Demo {
    public static void main(String[] args) {
        /*
        * 1.需求
        * 给定一个整数数组 nums 和一个整数目标值target，请你在该数组 中找出 和为目标值 target 的那 两个整数，并返回它们的数组下标。
        * 你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。 你可以按任意顺序返回答案。
        * 示例 1: 输入:nums =[2,7,11,15]，target = 9 输出:[0，1] 解释:因为nums[0]+nums[1]==9，返回[0，1]。
        * 示例 2: 输入:nums=[3,2,4]，target =6 输出:[1，2]
        * 示例 3: 输入:nums=[3,3]，target =6 输出:[0，1]
        * 提示: 2<= nums.length <= 10 。-109 <= nums[i]<= 109 -109 <= target <= 109 。
        * 只会存在一个有效答案
        *
        * 2.实现思路
        * 哈希表：使用一个哈希表（HashMap）来存储数组中已经访问过的元素及其对应的下标。
        * 遍历数组：对于每个元素，计算目标值与当前元素的差值。
        * 查找哈希表：检查差值是否在哈希表中存在。
        * 如果存在，说明找到了两个数，它们的和为目标值，返回它们的下标。
        * 如果不存在，将当前元素及其下标存入哈希表中。
        * 返回结果：如果遍历结束后没有找到符合条件的两个数，则返回空数组（根据题意，这种情况不会发生）。
        * */
        //测试第一组
        int[] nums = {2,7,11,15};
        int target = 9;
        int[] result = twoSum(nums,target);
        System.out.println(Arrays.toString(result));
        //测试第二组
        int[] nums1={3,2,4};
        int target1=6;
        int[] result1= twoSum(nums1,target1);
        System.out.println(Arrays.toString(result1));
        //测试第三组
        int[] nums2={3,3};
        int target2=6;
        int[] result2= twoSum(nums2,target2);
        System.out.println(Arrays.toString(result2));
    }
    public  static int[] twoSum(int[] nums ,int target){
        //创建一个哈希表,用于存储已经访问过的元素以及其对应的下标
        Map<Integer, Integer> numMap = new HashMap<>();
        //遍历数组
        for(int i=0;i<nums.length;i++){
            //计算目标值与当前元素的差值
            int complement=target-nums[i];
            //检查差值是否存在哈希表中
            if(numMap.containsKey(complement)){
                //存在，说明找到了两个数，和为目标值，返回它们的下标
                return new int[]{numMap.get(complement),i};
            }
            //不存在，将当前元素及下标存在哈希表中
            numMap.put(nums[i],i);
        }
        //遍历结束后，没有找到符合条件的两个数，返回空数组
        return new int[] {};
    }
}