题目（英文版）

[LeetCode] 1. Two Sum 两数之和

 

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

题目的中文意思：

给定一个整数数组，然后在给定一个数，要求数组的两个数加起来要等于给定的数，然后返回数组相加两个数字的索引。

您可以假设每个输入都只有一个解决方案，并且不能两次使用相同的元素。

例子：

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1].

---

解答：

解法一（用暴力**的方式）：

暴力**思路：

 暴力**的代码：

public class Main {
    //定义一个找下标方法twoSum
    public static void twoSum(int[] num,int sum){
        //定义一个中间变量temp，用来存储两个相加要找的第二个数
        //比如2是数组的第一个数，9-2=7
        //我们知道我们要存的第二个数为7
        int temp;
        //开始循环，首先第一次循环找出两数相加的第一个数
        //比如我们这里的2
        for(int i = 0;i<num.length;i++){
            //确定要找的第二个数，比如我们这里的7
            temp = sum - num[i];
            //第二层循环，注意是要从i开始后面的数中找。在数组中找到7
            for(int j = i+1;j<num.length;j++){
                //找到了
                if(num[j]==temp){
                    //打印出下标
                    System.out.println(i+"-"+j);
                    //退出方法
                    return;
                }
            }
        }
    }

    public static void main(String[] args) {
        //测试数据
        int[] a = new int[]{2,3,1,4,2,7};
        //测试数据
        int sum = 9;
        twoSum(a,9);
    }
}

但用暴力**方法的时间复杂度为O（n^2）,空间复杂度为O（1）.

下面我们介绍另一种解法：

借助Map的方式：

 代码：

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

public class Main {
    //定义一个找下标方法twoSum
    public static int[] twoSum(int[] num,int sum){
        //定义有两个值的result数组，用来存储两个相加数的下标
        int[] result = new int[2];
        //判断，如果数组没有数或只有一个数，那不存在这样的下标
        if((num == null) || num.length<1) return result;
        //定义存储数组数和下标的Map
        Map<Integer,Integer> map = new HashMap<Integer, Integer>();
        //循环
        for(int i=0;i<num.length;i++){
            //一次判断数组的数，比如这里假设是第一个数2
            int n = num[i];
            //求出要的第二个数
            int temp = sum - n;
            //判断Map中是否存在这样的数
            if(map.containsKey(temp)){
                //存在返回结果
                result[0] = i;
                result[1] = map.get(temp);
                return result;
            }else{
                //不存在则将该数存到Map，以便下次循换判断
                map.put(n,i);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        //测试数据
        int[] a = new int[]{3,1,4,2,7};
        //测试数据
        int sum = 9;
         int[] res = new int[2];
         res = twoSum(a,sum);
        System.out.println(res[0]+"-"+res[1]);
    }
}

这是使用了一个Map，用空间换取时间，因为循环只遍历一次

所以时间复杂度为O（n）,空间复杂度为O（n）

上面的暴力**时间复杂度为O（n^2）,空间复杂度为O（1）

在现在对时间效率要求高的话，第二种解法可能会好一点。

---

好了，本次的分享到此结束，有错误的地方欢迎大家下方留言。

如果觉得本分享对您有帮助的话，希望你能给我点个关注或喜欢QWQ，作为我创作的动力。

如果有不理解的在下方留言，我会及时回复的。