[record of question brushing] 1 Sum of two numbers

Preface

By taking part in the monthly change activities , Let's go over the algorithm again , At the same time, see if you can generate some new ideas .

One 、 Title Description

Given an array of integers  nums  And an integer target value  target, Please find... In the array   And is the target value  target   the   Two   Integers , And return their array subscripts .

You can assume that each input corresponds to only one answer . however , The same element in the array cannot be repeated in the answer .

You can return the answers in any order

source ：

Power button （LeetCode）

Example  1：

  Input ：nums = [2,7,11,15], target = 9
  Output ：[0,1]
  explain ： because  nums[0] + nums[1] == 9 , return  [0, 1] .


Example  2：

Input ： nums = [3,2,4], target = 6
Output ： [1,2]


Tips ：

• 1 <= s.length <= 1000

• s
    By the English letters （ Lowercase and upper case ）、
  ','
    and  
  '.'
    form

• 1 <= numRows <= 1000

Two 、 Thought analysis ：

1. Simple direct violent solution  -  Traverse

If you don't think too much , If we want to find the sum of two numbers in an array is  

target

Then the most direct way is   For each

nums[i]

  Traversal array , See if there is something that can satisfy  

nums[i] + nums[j] == target

Code implementation

class Solution {
 public int[] twoSum(int[] nums, int target) {
 int length = nums.length;
 // Guarantee num[j] There is  i  Traversing  n-2  until
 for (int i = 0; i < length - 1; i++) {
 // Avoid repetition , The traversal starts after the current array
 for (int j = i + 1; j < length; j++) {
 if (nums[i] + nums[j] == target) return new int[]{i,j};
 }
 }
 return new int[]{};
 }
}


For the current solution

Time complexity ：

Spatial complexity ：

Running results

2. Improve the solution - Hashtable

From the above time complexity and the actual running time . The time of this kind of violence is the simplest and most direct , But it also takes more time .

The main reason for consuming time is also for   every last

num[i]

, We need to find

target - num[i]

  Whether there is , And in the process of searching, it will repeatedly traverse the array many times .

So in order to reduce this unnecessary repeated traversal . We can store the value and subscript of each number in the array in a hash table

such , For each num[i], We can judge quickly

target - num[i]

  Whether there is , And get the subscript of the array .

Implementation code

class Solution {
 public int[] twoSum(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[]{};
 }
}


For the current solution

Time complexity ：

Spatial complexity ：

Running results

It can be seen that in a long time , Much shorter .

summary

When facing a problem , We don't have to do it directly in one step , We can start with the most direct . And then on this basis , Then find out if there is anything we can further optimize .