LOADING STUFF...
世界已冷酷至极, 让我们携手前行。
自助收录

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

算法刷题2年前 (2023)更新 江南白衣
365 0 0
使用单个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];
    }
}

 

© 版权声明

相关文章

开发者导航新手教程

暂无评论

暂无评论...