使用单个for循环解决“两数之和”问题

题目：两数之和
描述：给定一个升序排列的整数数组numbers，从数组中找出两个数满足相加之和等于目标数target。
注意：假设每个输入只对应唯一的答案，而且不可以重复使用相同的元素，返回两数的下标值，以数组形式返回。
思路：上篇我们用双重for循环解决了两数之和问题。但是这个算法有个缺陷，就是时间复杂度太高。算法题主要考虑时间复杂度，我们要尽量想办法降低时间复杂度，而无需考虑空间复杂度，因为现在计算机内存基本是够用的。这次我们使用单个for循环解决这个问题。此种方法的时间复杂度 < 二分法 < 双重for循环，是三种方式中的最优解。
1、定义map，存放已经遍历的元素，key:元素值，value:元素索引。
2、遍历数组，当前遍历元素是nums[i]，那么我们要找的元素是target – nums[i]，所以只要能满足条件：map.containsKey(target – nums[i])即key=target – nums[i]也在集合中，就可以终止循环。
3、如果集合中没有target – nums[i]，我们先将当前遍历元素加入集合，然后继续遍历数组，直到满足条件即可。

package od;

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

/**
 * 两数之和
 * 给定一个升序排列的整数数组numbers，从数组中找出两个数满足相加之和等于目标数target。
 * 假设每个输入只对应唯一的答案，而且不可以重复使用相同的元素。
 * 返回两数的下标值，以数组形式返回。
 * 原文地址：https://www.codernav.com/2825.html
 * 更多算法详解：https://www.codernav.com
 */
public class OdTest23 {
    public static void main(String[] args) {
        int[] result = f(new int[]{1, 2, 3, 4, 5, 6}, 10);
        System.out.println(Arrays.toString(result));
    }

    private static int[] f(int[] nums, int target) {
        // 定义map，存放已经遍历的元素，key:元素值，value：元素索引
        Map<Integer, Integer> map = new HashMap<>();
        // 遍历数组
        for (int i = 0; i < nums.length; i++) {
            // 当前遍历元素是nums[i]，我们要找的元素是target - nums[i]
            if (map.containsKey(target - nums[i])) {
                return new int[]{map.get(target - nums[i]), i};
            }
            // 如果集合中没有target - nums[i]，将元素加入集合，继续遍历，直到满足条件
            map.put(nums[i], i);
        }
        return new int[0];
    }
}