LeetCode-1. Sum of two numbers (day1)

Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities.

I. Preface:

👨🎓 Author: Bug Bacteria

✏️ blog: CSDN, Nuggets, etc

💌 public account: Magic House of the Circle of the Apes

🚫 special statement: original is not easy, reprint please attach the original source link and this article statement, thank you for your cooperation.

🙏 Copyright notice: part of the text or pictures in the article may come from the Internet or Baidu Encyclopedia, if there is infringement, please contact bug bacteria processing.

Hello, little friends, I am bug bacteria 👀. Gold three silver four, brush the month again. So whether you’re looking for a career change or a career change, get your act together and do the right thing 👣. So, quickly follow the pace of bug bacteria roll up ⏰, strong from this moment! ➕ 🧈

In the process of reviewing articles, if you think the articles are helpful to you at all, please don’t be too mean with your likes and bravely light up the articles 👍. Your likes (collect ⭐️+ pay attention to 👨 port + message board) are the best encouragement and support for bugs on my creation path. Time does not abandon 🏃🏻♀️, nuggets stop 💕, cheer up 🏻

Ii. Title Description:

Given an array of integers nums and an integer target value target, find the two integers in the array and the target value target, and return their array subscripts.

You can assume that there is only one answer for each type of input. However, the same element in the array cannot be repeated in the answer. You can return the answers in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9 output: [0,1]Copy the code

Example 2:

Input: nums = [3,2,4], target = 6Copy the code

Title: LeetCode website

Difficulty: ⭐

Iii. Analysis of Ideas:

Idea 1: Enumeration of violence

Accustomed to violence students see this problem, the easiest way to think of is to use violence to solve all problems. If there is an array with two subscripts, return an empty array. If there is an array with two subscripts, return an empty array.

When you are iterating through the array looking for a number (target-num), note that every element before num has already matched num, so there is no need to repeat the match. Num is used only once, and then target-num is found in the inner loop.

Idea 2: Hash table method

You may have noticed that the time complexity of the idea 1 query (target-num) is high. So we can do it using a hash table.

If num does not exist, insert num into the hash table. If num does exist, return.

Iv. Algorithm implementation:

Violence enumeration method _AC code

The specific code is as follows:

class Solution { public int[] twoSum(int[] nums, int target) { for(int i=0; i<nums.length; Int num = target-nums [I]; // start with I +1; for(int j = i+1; j<nums.length; If (num == nums[j]){return new int[]{I, j}; Return new int[0]; return new int[0]; }}Copy the code

Complexity analysis:

Time complexity: O(N^2), where N is the number of elements in the array. In the worst case, any two numbers in the array must be matched once.
Space complexity: O(1)

Hash table method _AC code

The specific code is as follows:

Class Solution {public int[] twoSum(int[] nums, int target) { Integer> map = new HashMap<Integer, Integer>(); for (int i = 0; i < nums.length; If (map.containsKey(target-nums [I])) {return new int[]{map.get(target-nums [I]), i}; } // Add num to map.put(nums[I], I); } return new int[0]; }}Copy the code

V. Summary:

Idea one violence enumeration method leetcode submitted running results screenshot as follows:

The results of leetcode submission are as follows:

To sum up, it is obvious that searching with map is more efficient, which improves the efficiency of target-num query. And if it were you, you would do the same thing.

Furthermore, there are thousands of ways to solve the problem. If you have any better ideas or ideas, please let me know in the comment section. We can learn from each other and grow faster.

Well, that’s all for this episode and I’ll see you next time.

Six, hot recommendations:

Leetcode -1. Sum of two numbers
Leetcode – 9. Palindrome
Leetcode -13. Roman numeral to integer
Leetcode -14. The longest public prefix
Leetcode -20. Valid parentheses
Leetcode -21. Merge two ordered lists
Leetcode -26. Remove duplicates from ordered arrays

Vii. End of article:

If you want to learn more, check out bug Bug’s daily Question LeetCode! Take you to brush together. One person may feel very tired and difficult to persist in brushing, but a group of people will think it is a meaningful thing to brush, urge and encourage each other, and become stronger together.

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

☘️ Be who you want to be, there is no time limit, you can start whenever you want,

🍀 You can change from now on, you can also stay the same, this thing, there are no rules to speak of, you can live the most wonderful yourself.