1. 两数之和（算法思维系列）

谁借莪１个温暖的怀抱￠ 2023-10-05 20:28 10阅读 0赞

#### 1. 两数之和 ####

*  题目
 *  解题思路
 *  代码

## 题目 ##

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

你可以按任意顺序返回答案。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]

## 解题思路 ##

最简单的方法就是暴力穷举。进阶一点就用一个Hash表来存放值和索引的映射，来减低时间复杂度。

或者可以给数组排序，然后用nSum的解题模板。具体代码见后续的15.三数之和。但是要注意啊！本题是不允许改变数组的顺序的，所以不能排序后用nSum模板

## 代码 ##

class Solution {
        
        public int[] twoSum(int[] nums, int target) {
        
            int n=nums.length;
            //记录元素值到索引的映射
            Map<Integer,Integer> index=new HashMap<>();
    
            for(int i=0;i<n;i++){
        
                index.put(nums[i],i);
            }
    
            for(int i=0;i<n;i++){
        
                int other=target-nums[i];
                //如果other在index中，并且不是nums[i]本身，就证明有满足条件的元素
                if(index.containsKey(other)&&index.get(other)!=i){
        
                    return new int[]{
        i,index.get(other)};
                }
            }
            return new int[]{
        -1,-1};
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210225230500918.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70