当前位置:网站首页>Leetcode-1. Sum of two numbers (Application of hash table)
Leetcode-1. Sum of two numbers (Application of hash table)
2022-07-05 12:20:00 【A finger leaf next to the giant】
Preface :
stay Leetcode First simple question - The sum of two numbers algorithm problem , I directly took violence to solve two levels for Cycle to solve the problem , Next, I'm in the discussion area , See a new solution , Take advantage of Map Containers , And in further understanding Map Container found , original Map Containers -hash_map The bottom of the set is the hash table , Hash table , This enables us to learn hash tables with java Medium hasMap Gather and associate to understand .
Let's look at the original question :
Given an array of integers nums And an integer target value target, Please find... In the array And is the target value the Two Integers , And return their array subscripts . You can assume that each input corresponds to only one answer . however , The same element in an array cannot be used twice .
You can return the answers in any order .
source : Power button (LeetCode)
First of all, mine
Violence solution :
The idea is easy to understand , It is through for The loop first determines a number , And then again for Whether the number after loop traversal is equal to the difference between its target value and the determined number .
class Solution {
public int[] twoSum(int[] nums, int target) {
int []a=new int[2];
int middle;
for(int i=0;i<nums.length;i++){
middle=target-nums[i];
for(int j=i+1;j<nums.length;j++){
if(nums[j]==middle){
a[0]=i;
a[1]=j;
return a;
}
}
}
return a;
}
}
Complexity analysis
Time complexity :O(N^2) among N Is the number of elements in the array . In the worst case, any two numbers in the array must be matched once .
Spatial complexity :O(1).
then , In the discussion area , It was proposed , Its comparison obviously has many repetitive results , In order to make every time for Cycles are more meaningful . We store the compared value and the corresponding subscript into hasMap Collection , And in the hasMap The efficiency of searching in the set is very high . Therefore, it introduces Map Concept of container .
about Map If the container has something you don't understand , Take a look at this article : Map Interpretation of container
Hash solution
It mainly uses hasMap aggregate , stay hasMap The query time complexity in the set is constant , Although it consumes a lot of memory space , But it has a good performance in terms of time efficiency .
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map = new HashMap<>();
int[] result = new int[2];
for (int i = 0; i < nums.length; i++) {
if(map.containsKey(target - nums[i])){
result[0] = i;
result[1] = map.get(target - nums[i]);
return result;
}
map.put(nums[i],i);
}
return result;
}
}
Complexity analysis
Time complexity :O(N), among N Is the number of elements in the array . because hasMap The query time complexity in the set is constant , For each element x, We can O(1) Looking for target - x.
Spatial complexity :O(N), among N Is the number of elements in the array . Mainly for the cost of hash table .
边栏推荐
- Acid transaction theory
- How does MySQL execute an SQL statement?
- A new WiFi option for smart home -- the application of simplewifi in wireless smart home
- Redis master-slave mode
- MySQL transaction
- 1. Laravel creation project of PHP
- mysql拆分字符串做条件查询
- Thoughts and suggestions on the construction of intelligent management and control system platform for safe production in petrochemical enterprises
- Redis's memory elimination mechanism, read this article is enough.
- Time tools
猜你喜欢
One article tells the latest and complete learning materials of flutter
Redis highly available sentinel cluster
MySQL storage engine
Tabbar configuration at the bottom of wechat applet
mmclassification 训练自定义数据
调查显示传统数据安全工具在60%情况下无法抵御勒索软件攻击
ABAP table lookup program
Thoughts and suggestions on the construction of intelligent management and control system platform for safe production in petrochemical enterprises
The survey shows that traditional data security tools cannot resist blackmail software attacks in 60% of cases
[cloud native | kubernetes] actual battle of ingress case (13)
随机推荐
Redis highly available slice cluster
Select drop-down box realizes three-level linkage of provinces and cities in China
查看rancher中debug端口信息,并做IDEA Remote Jvm Debug
[untitled]
Linux安装部署LAMP(Apache+MySQL+PHP)
byte2String、string2Byte
Get all stock data of big a
ZABBIX customized monitoring disk IO performance
Why do you always fail in automated tests?
Solution to order timeout unpaid
MySQL splits strings for conditional queries
你做自动化测试为什么总是失败?
JS for循环 循环次数异常
自动化测试生命周期
Video networkState 属性
About cache exceptions: solutions for cache avalanche, breakdown, and penetration
[cloud native | kubernetes] actual battle of ingress case (13)
Read and understand the rendering mechanism and principle of flutter's three trees
Learn JVM garbage collection 05 - root node enumeration, security points, and security zones (hotspot)
Matlab imoverlay function (burn binary mask into two-dimensional image)