Leetcode 30天高效刷数据结构和算法 Day1 两数之和 —— 无序数组

本文涉及的产品
实时计算 Flink 版,5000CU*H 3个月
检索分析服务 Elasticsearch 版,2核4GB开发者规格 1个月
大数据开发治理平台 DataWorks,不限时长
简介: 给定一个无序整数数组和目标值,找出数组中和为目标值的两个数的下标。要求不重复且可按任意顺序返回。示例:输入nums = [2,7,11,15], target = 9,输出[0,1]。暴力解法时间复杂度O(n²),优化解法利用哈希表实现,时间复杂度O(n)。

两数之和 —— 无序数组

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1:

输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
示例 2:

输入:nums = [3,2,4], target = 6
输出:[1,2]
示例 3:

输入:nums = [3,3], target = 6
输出:[0,1]

两数之和问题解法

1. 暴力解法

代码

public static int[] twoSum(int[] nums, int target) {
   
    for(int i=1;i<nums.length;i++){
   
        for (int j=0; j<i; j++) {
   
            if(nums[i]+nums[j]==target){
   
                return new int[]{
   j,i};
            }
        }
    }
    return new int[0];
}

时间复杂度

O(n²)

2. 优化

优化思路

如果要同时判断符合条件的i和j是否存在数组中,则必定需要使用双层循环,时间复杂度为O(n²)+。
因此我们可以考虑将另一个参数表示为target-x(x为第一个参数)。
为了判断是否存在,考虑使用哈希表,来存储数组元素:元素下标,Map就是典型的空间换时间
此时我们最多遍历一次数组,因此优化后的时间复杂度为O(n)

代码

public static int[] twoSum1(int[] nums, int target) {
   
    Map<Integer,Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
   
        if(map.containsKey(target-nums[i])){
   
            return new int[]{
   map.get(target-nums[i]),i};
        }
        map.put(nums[i],i);
    }
    return new int[]{
   0};
}

时间复杂度

O(n)

目录
相关文章
|
7天前
|
存储 算法 Go
算法学习:数组 vs 链表
算法学习:数组 vs 链表
13 0
|
2天前
|
存储 JavaScript 前端开发
JavaScript中的数组是核心数据结构,用于存储和操作序列数据
【6月更文挑战第22天】JavaScript中的数组是核心数据结构,用于存储和操作序列数据。创建数组可以使用字面量`[]`或`new Array()`。访问元素通过索引,如`myArray[0]`,修改同样如此。常见方法包括:`push()`添加元素至末尾,`pop()`移除末尾元素,`shift()`移除首元素,`unshift()`添加到开头,`join()`连接为字符串,`slice()`提取子数组,`splice()`进行删除、替换,`indexOf()`查找元素位置,`sort()`排序数组。还有其他如`reverse()`、`concat()`等方法。
8 2
|
7天前
|
算法 Java
[Java·算法·简单] LeetCode 283. 移动零
[Java·算法·简单] LeetCode 283. 移动零
16 2
|
7天前
|
算法 Java
[Java·算法·中等] LeetCode21. 合并两个有序链表
[Java·算法·中等] LeetCode21. 合并两个有序链表
14 2
|
10天前
|
存储 算法 调度
力扣中级算法(Python)
力扣中级算法(Python)
|
10天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
10天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
10天前
|
算法 索引 Python
数据结构 数组部分小结
数据结构 数组部分小结
|
10天前
|
C++ Python
二刷力扣--数组
二刷力扣--数组
|
16小时前
|
存储 算法 Java
Java数据结构与算法:线性数据结构之数组
Java数据结构与算法:线性数据结构之数组
4 0