IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> NC61 两数之和 -> 正文阅读

[数据结构与算法]NC61 两数之和

描述

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

要求:空间复杂度 O(n)O(n),时间复杂度 O(nlogn)O(nlogn)
在这里插入图片描述

解题

使用HashMap

  • 题目要求的是O(nlogn),那么显然遍历两次的方法是不行的,因此这里使用到了哈希表的方法
  • 注意!不用存和找分开两次for进行!
  • 可以一遍for就可以,查找,存在则返回,不存在则存储
  • 注意值作为key存储,下标当做value
  • 这样也不用考虑数组重复的问题,因为先查找,如果有的话都不用存直接返回一个数组就不会存在重复的值的问题!
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = new int[]{3, 2, 4};
        int[] ints = solution.twoSum(arr, 6);
        for (int i : ints) {
            System.out.print(i + " ");
        }
    }

    public int[] twoSum(int[] arr, int target) {
         // <value,index>
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if (map.containsKey(target - arr[i])) {
                return new int[]{map.get(target - arr[i]) + 1, i + 1};
            } else {
                map.put(arr[i], i);
            }
        }
        return new int[0];
    }
}
  数据结构与算法 最新文章
【数据结构】二叉查找树/二叉搜索树BST(附
二叉树的前序后续中序遍历(迭代)(C++)
【贪心算法】手办合并
LeetCode 每日一题——462. 最少移动次数使
leetcode47. 全排列 II
Java二叉树
线性结构(一)
【Java版算法思想(排序)】选择&冒泡&
LeetCode系列49—字母异位词分组
NC78 反转链表
上一篇文章      下一篇文章      查看所有文章
加:2022-01-17 11:44:21  更:2022-01-17 11:46:43 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
360图书馆 购物 三丰科技 阅读网 日历 万年历 2022年5日历 -2022/5/24 5:33:49-
图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码