数组中两数之和

描述

给出一个整数数组,请在数组中找出两个加起来等于目标值的数,

你给出的函数twoSum 需要返回这两个数字的下标(index1,index2),需要满足 index1 小于index2.。注意:下标是从1开始的

假设给出的数组中只存在唯一解

例如:

给出的数组为 {20, 70, 110, 150},目标值为90
输出 index1=1, index2=2

示例1

输入:

[3,2,4],6

复制返回值:

[2,3]

复制说明:

因为 2+4=6 ,而 2的下标为2 , 4的下标为3 ,又因为 下标2 < 下标3 ,所以输出[2,3]

方法一:直接遍历

具体做法:
循环遍历数组的每一个数,如果遍历的两数之和等于target,则返回两个数的下标;

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

import java.util.*;

public class Solution {

    /**

     *

     * @param numbers int整型一维数组

     * @param target int整型

     * @return int整型一维数组

     */

    public int[] twoSum (int[] numbers, int target) {

        // write code here

        int n = numbers.length;

        int[] res = {-1, -1};

        //遍历数组

        for (int i = 0; i < n; ++i) {

            for (int j = i + 1; j < n; ++j) {

                //判断相加值是否为target

                if (numbers[i] + numbers[j] == target) {

                    res[0] = i+1;

                    res[1] = j+1;

                    //返回值

                    return res;

                }

            }

        }

        return res;

    }

}

复杂度分析:

  • 时间复杂度:O(n^2) 遍历两次数组
  • 空间复杂度:O(1) 未申请额外空间

方法二 hash表

具体做法:
使用Map来降低时间复杂度,遍历数组,如果没有 (target - 当前值) 就将当前数字存入哈希表,如果有,返回该数字下标即可。

哈希表可以优化第二遍循环中对元素的检索速度,
具体过程如下图所示:

数组中两数之和

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

import java.util.*;

public class Solution {

    /**

     *

     * @param numbers int整型一维数组

     * @param target int整型

     * @return int整型一维数组

     */

    public int[] twoSum (int[] numbers, int target) {

        // write code here

        HashMap<Integer, Integer> map = new HashMap<>();

        //遍历数组

        for (int i = 0; i < numbers.length; i++) {

            //将不包含target - numbers[i],装入map中,包含的话直接返回下标

            if(map.containsKey(target - numbers[i]))

                return new int[]{map.get(target - numbers[i])+1, i+1};

            else

                map.put(numbers[i], i);

        }

        throw new IllegalArgumentException("No solution");

    }

}

 

上一篇:方法


下一篇:python之循环