“This is the second day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

Always thinking of starting to brush questions, even if it is not out of the interview, but also exercise logic, but always give up halfway

As a student with poor academic performance, I often couldn’t even remember the first abandon when I was used as a word in high school English. This is just like the first question of the current force link algorithm. I remember that I actually read the idea many years ago, but now I find that it is still stumbling

Then take advantage of the gold digging activities, combine some questions with their own understanding, ensure the speed of a question every day to the Spring Festival, as proof

Abandon in the word list

All things are difficult at the beginning, now start with the first word, which itself is not difficult, so start with him

two sum

The title

Given an integer array 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.

The sample

Example 1:

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

Input: nums = [3,2,4] target = 6 output: [1,2] example 3:

Input: nums = [3,3], target = 6

Train of thought

The most straightforward solution, of course, is the two-layer for loop, which is O(n*n) complexity. In order to get the feel of the handwriting algorithm and get rid of the IDE tool, alai, still start writing from this loop

To achieve 1

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[i] + nums[j] == target) {
                return new int[]{i, j}; }}}return new int[0];
}
Copy the code
Commit the result execution time memory consumption through 56 ms 38.7 MBCopy the code

Plain and unpretentious, clear and easy to understand, but the interview question might just go home

The 2

The disadvantage of implementation 1 is that the algorithm is highly responsible, and this is not necessary

The first loop actually found all the values needed, the second loop is unnecessary

So the next step is to go through the loop to find the answer,

The most straightforward way to think about it is to store the iterated data in the hash during the loop

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> data = new HashMap<>(nums.length);
    for (int i = 0; i < nums.length; i++) {
        int t = target - nums[i];
        if (data.containsKey(t)) {
            return new int[]{data.get(t), i};
        } else{ data.put(nums[i], i); }}return new int[0];
}
Copy the code
Commit results execution time memory consumption through 2 ms 38.1 MBCopy the code

This implementation uses Hash to get elements with O(1) complexity

This allows you to iterate through the loop to find the elements that match the criteria

The lines

This problem gives me the impression that reasonable use of the characteristics of data structure can greatly reduce the complexity of the algorithm and improve the processing efficiency

The choice of data structure is also very important, including in actual development

In business, for example,

Input -> output

0 – > 0

1 – > 1,

2 – > 1,

3 – > 2,

4 – > 3,

5 – > 5

In this case, the business can be implemented by storing the correspondence, which is often referred to as table-driven

private static final int[] data = {0.1.1.2.3.5};

public int getResult(int n) {
    if (n < 0 || n > data.length) {
        return -1;
    }
    return data[n];
}
Copy the code

All things are difficult at the beginning, come on ~ I said to myself

Learn more today and ask less tomorrow