Today is day 20 of Kevin’s algorithm. Let’s explain LeetCode problem 1, which is a simple but fairly classic problem.

Every day a smile

Play the game for the first time to pit a friend: SORRY, I didn’t mean to.

Second pit friend: EMMM

Third pit friend: hey hey hey

Fourth pit friend: why are you so pit?

Topic describes

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

You can assume that there is only one answer for each type of input. However, the same element in an array cannot be used twice.

Example:

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

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

Source: LeetCode Link: https://leetcode-cn.com/problems/two-sum Copyright belongs to The Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Their thinking

Violence law

Iterate over each element x and find if there is a target element with a value equal to target-x.

//go
func twoSum(nums []int, target int) []int {
    length := len(nums)
    ans := make([]int.0)
    for i := 0; i<length; i++ {
 for j := i+1; j<length; j++ {  if nums[i] + nums[j] == target{  ans = append(ans, i, j)  }  }  }  return ans } Copy the code
//java
class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
 if (nums[j] == target - nums[i]) {  return new int[] { i, j };  }  }  }  throw new IllegalArgumentException("No two sum solution");  } } Copy the code

Complexity analysis:

  • Time complexity: O(n^2)
  • Space complexity: O(1)

Hash table method

By trading space for speed, we can reduce the search time from O(n) to O(1). Hash tables are built for this purpose, enabling quick lookups in approximately constant time.

We can add the value of each element and its index to the hash table, and then check whether the target element (target-nums [I]) corresponding to each element is present in the table during traversal. Note that ⚠️, the target element cannot be nums[I] itself!

//go
func twoSum(nums []int, target int) []int {
    result := make([]int.0)
    m := make(map[int]int, length)
    for i,k := range nums{
 // Check whether a value with key [target-k] exists in the map  ifvalue,exist := m[target - k]; exist && value ! = i{ // append: tail append element  result = append(result,value)  result = append(result, i)  }  m[k] = i  }  return result } Copy the code
//java
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
 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");  } } Copy the code

Solemnly declare:

The code shown has been passed by LeetCode, please rest assured to eat ~

In the front teeth

Many of us try to form good habits, but most of us don’t. In order for us to stick together, we decided to make the following plan (benefits).

Learn algorithms together, punch and get red envelopes!

Participation:

Follow my wechat official account “Kevin’s School”

And with lots of friends

Stick together, learn together, better together!

The rules are:

“Message” “punch XXX days” ➕ “share” to the circle of friends

Reward:

Continuous clocking 21 days, contact me to get 6.6 yuan a red envelope!

Continuous clocking 52 days, contact me to get 16.6 yuan a red envelope!

Continuous clocking 100 days, contact me to get 66.6 yuan a red envelope!

Personal energy is not enough, the content is mainly published on the public platform, other platforms may not update in time, please forgive me ~