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

1. 两数之和

• 题目
• 解题思路
• 代码

题目

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

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

你可以按任意顺序返回答案。

解题思路

最简单的方法就是暴力穷举。进阶一点就用一个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};
    }
}