题意整理

  • 给出一个整型数组 numbers 和一个目标值 target，在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。
  • 数组下标从1开始算。

方法一（暴力）

1.解题思路

利用两层循环遍历所有可能的两个数的组合，第一层遍历所有元素，第二层遍历当前元素之后的所有元素，如果满足两数之和等于target，直接返回对应的下标。

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 
     * @param numbers int整型一维数组 
     * @param target int整型 
     * @return int整型一维数组
     */
    public int[] twoSum (int[] numbers, int target) {
        //第一个数和第二个数的下标
        int index1=0;
        int index2=0;
        int n=numbers.length;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                //如果两个数之和等于target，返回对应下标数组
                if(numbers[i]+numbers[j]==target){
                    return new int[]{i+1,j+1};
                }
            }
        }
        return new int[]{-1,-1};
    }
}

3.复杂度分析

  • 时间复杂度：两层循环，总共需要执行n∗(n−1)/2n*(n-1)/2次，所以时间复杂度为O(n2)O(n^2)。
  • 空间复杂度：需要额外常数级别的空间，所以空间复杂度是O(1)O(1)。

方法二（哈希表）

1.解题思路

可以利用一个map存储数组中的数字，以及对应的下标，当遍历到某个数时，如果map中已经包含target−numbers[i]target-numbers[i]的键，说明之前存在一个数target−numbers[i]target-numbers[i]，这个数加上当前数字numbers[i]numbers[i]正好等于target。所以可以直接返回对应的下标。

图解展示： alt

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 
     * @param numbers int整型一维数组 
     * @param target int整型 
     * @return int整型一维数组
     */
    public int[] twoSum (int[] numbers, int target) {
        //新建map，键为数组中某一个数，值为对应下标
        HashMap<Integer,Integer> map=new HashMap<>();
        //第一个数和第二个数的下标
        int index1=0;
        int index2=0;
        int n=numbers.length;
        for(int i=0;i<n;i++){
            //如果包含target-numbers[i]，说明存在一个数与numbers[i]之和等于target
            if(map.containsKey(target-numbers[i])){
                //记录两个数的下标
                index1=map.get(target-numbers[i]);
                index2=i;
                return new int[]{index1+1,index2+1};
            }
            //将当前数字放入map
            map.put(numbers[i],i);
        }
        return new int[]{-1,-1};
    }
}

3.复杂度分析

  • 时间复杂度：只需遍历数组一次，所以时间复杂度为O(n)O(n)。
  • 空间复杂度：需要额外大小为n的哈希表，所以空间复杂度是O(n)O(n)。