This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

1. Title Description

The sum of two Numbers

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.

You can return the answers in any order.

Example 1:

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

Example 2:

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

Example 3:

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

Second, train of thought analysis

violence

  • The question should be simple and clear. Let’s find the subscript of the specified array and the specified number. And the array length is greater than or equal to 2. So we don’t have to worry about the array extremes.
  • The first thought would be brute force. Brute force is undeniably a viable option in this case. We’re just going to iterate through what’s going on and what’s going on and see if it fits and if it does, we’re going to return it

hash

  • Brute force cracking wastes time because we need to constantly compare the data behind the current element, which we can do with hashes
  • First, we can add the data to the hash once, just looking for the difference in the map each time we iterate over the data. If it can be found, it means that there is data in the array that meets the condition. At this time, we can return the index of the original array

AC code

violence

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 (target == nums[i] + nums[j]) {
                return new int[]{i, j}; }}}return new int[2];
}
Copy the code

hash

public int[] twoSum(int[] nums, int target) {
    int[] arr = new int[2];
    int index = 0;
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; i++) {
        int sub = target - nums[i];
        if(map.containsKey(sub) && i ! = map.get(sub)) { arr[0] = i;
            arr[1] = map.get(sub);
            break; }}return arr;
}
Copy the code

Hash upgrade

  • Hash is basically the same as violence in general. It’s a little high in memory consumption. But a closer look at the code above shows that there is room for improvement. We’re still not really out of the loop.
  • There is no need to populate the hash table first. We can populate the map while doing validation

  • With a slight shift in thinking we can avoid multiple loops. The above comparison of our code is as follows
public int[] twoSum3(int[] nums, int target) {
    int[] arr = new int[2];
    int index = 0;
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int sub = target - nums[i];
        if(map.containsKey(sub) && i ! = map.get(sub)) { arr[0] = i;
            arr[1] = map.get(sub);
            break;
        }
        map.put(nums[i], i);
    }
    return arr;
}
Copy the code

Four,

  • Brute force cracking is normally not something we should use, but sometimes brute force cracking is not an option. In this case, the violence solution can be used completely
  • Hash is often stored in data from scratch, and is used by subsequent locating elements

Like, follow and bookmark