This is the second day of my participation in the August Text Challenge.More challenges in August

Topic describes

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. The sample1: Input: nums = [2.7.11.15], target = 9Output:0.1Because nums[0] + nums[1] = =9To return to the [0.1]. The sample2: Input: nums = [3.2.4], target = 6Output:1.2] example3: Input: nums = [3.3], target = 6Output:0.1] :2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109There will only be one order of valid answers: can you come up with an algorithm whose time complexity is less than O(n2)? .Copy the code

Ideas & CODE

1. Brute force cracking

They say there are two numbers in the array whose sum is equal to the parameter target passed in, and there must be only one pair of those numbers. The first thing that comes to mind is a double for loop, summing up all the numbers in the array with numbers that are different from you, and returning the index once the sum equals target

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 null;
}
Copy the code

But obviously this time complexity is O(n), and we need a more efficient method

2. A hash table

I didn’t think of hashing at first, but I had to look at the solution.

Above we did a double for loop: the first loop iterated through all the data, which was definitely unavoidable; The second for loop again iterates over the data in the set that differs from the first loop and compares the sums. So the key is the second loop, how to get rid of the second loop? The answer is hashing

  • We start with the first for loop
  • Target - The array value currently traversedThat’s another array value that we’re going to find, and we’re going to look for that key in our hash table
  • If there is an index in the hash table, return the index and the current traversal index
  • If not, the iterated value is stored in the hash table as key and the index as value
  • Note that storing into the hash table should be done at the end, otherwise duplicate values will be fetched, for exampleArray: [3, 3] target: 6, it is possible to return an index of[0, 0], the correct return should be[0, 1]
public int[] twoSum2(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 null;
}
Copy the code

And then the time is order one