Shulou(Shulou.com)06/02 Report--

Editor to share with you how LeetCode to achieve the sum of two numbers, I believe that most people do not know much about it, so share this article for your reference, I hope you can learn a lot after reading this article, let's go to understand it!

Title:

Given an array of integers nums and a target value target, please find the two integers in the array that are the target values and return their array subscript.

You can assume that each input corresponds to only one answer. However, you cannot reuse the same elements in this array.

Example:

Given nums = [2,7,11,15], target = 9

Because nums [0] + nums [1] = 2 + 7 = 9

So return [0,1]

This is a question of the sum of two numbers, which seems very simple. Readers can think about how to achieve it first. This paper introduces three implementation methods and analyzes the complexity.

1. Violence method

The method of violence is simple. Iterate through each element xx and find out if there is a target element with a value equal to target-xtarget − x. The code example is as follows:

Public int [] twoSum (int [] nums, int target) {

Int [] result = new int [2]

For (int I = 0; I < nums.length; iTunes +) {

For (int j = I + 1; j < nums.length; jacks +) {

If (Nums [I] + nums [j] = = target) {

Result [0] = I

Result [1] = j

Return result

}

}

}

Return result

}

Algorithm complexity analysis:

Time complexity: O (n ^ 2), for each element, we try to find the corresponding target element by traversing the rest of the array, which will take O (n) time. So the time complexity is O (n ^ 2).

Space complexity: O (1).

two。 Hash table twice

In order to optimize the runtime complexity, we need a more efficient way to check whether there are target elements in the array. If it exists, we need to find its index. What is the best way to keep each element in an array corresponding to its index? Hash table.

By exchanging space for speed, we can reduce the search time from O (n) to O (1). The hash table is built for this purpose, and it supports fast lookups at approximately constant times. I use "approximate" to describe it because in the event of a conflict, the search time may degenerate to O (n). But as long as you select the hash function carefully, the time it takes to look up in the hash table should be amortized to O (1).

A simple implementation uses two iterations. In the first iteration, we add the value of each element and its index to the table. Then, in the second iteration, we will check whether the target element corresponding to each element (target-nums [I]) exists in the table. Note that the target element cannot be nums [I] itself!

Public int [] twoSum (int [] nums, int target) {

Map map = new HashMap ()

For (int I = 0; I < nums.length; iTunes +) {

Map.put (nums [I], I)

}

For (int I = 0; I < nums.length; iTunes +) {

Int complement = target-nums [I]

If (map.containsKey (complement) & & map.get (complement)! = I) {

Return new int [] {I, map.get (complement)}

}

}

Throw new IllegalArgumentException ("No two sum solution")

}

Complexity analysis:

Time complexity: O (n), we traverse the list of n elements twice. Because the hash table reduces the lookup time to O (1), the time complexity is O (n).

Space complexity: O (n), the extra space required depends on the number of elements stored in the hash table, which stores n elements.

3. Hash table once

Facts have proved that we can do it all at once. While iterating and inserting the element into the table, we also go back to check whether the target element corresponding to the current element already exists in the table. If it exists, then we have found the corresponding solution and return it immediately.

Public int [] twoSum (int [] nums, int target) {

Map map = new HashMap ()

For (int I = 0; I < nums.length; iTunes +) {

Int complement = target-nums [I]

If (map.containsKey (complement)) {

Return new int [] {map.get (complement), I}

}

Map.put (nums [I], I)

}

Throw new IllegalArgumentException ("No two sum solution")

}

Complexity analysis:

Time complexity: O (n), we only iterated through the list containing nn elements once. Each lookup in the table takes only O (1) time.

Space complexity: O (n), the extra space required depends on the number of elements stored in the hash table, which needs to store up to n elements.

These are all the contents of the article "how to achieve the Sum of two numbers in LeetCode". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.