1. The subject

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

Tip:

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • There can only be one valid answer

Advanced: Can you think of an algorithm whose time complexity is less than O(n²)?

2. The answer

2.1 Violent solution

In a bubbling fashion, the sum is calculated in pairs using a double loop to get the result

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    result[0] = i;
                    result[1] = j;
                    returnresult; }}}returnresult; }}Copy the code

Time complexity

Because of the nesting of the loop, the interpretation block is executed n² times, so: O(n²)

Spatial complexity

The result array is initialized at the start of the function execution, and no additional space is occupied. Constant space complexity: O(1)

Submit the results

Try to optimize the

How can I reduce the time complexity to less than O(n ^ 2)?

Idea 1:

To sort an array, use a double pointer before and after, sort using a time complexity of O(nlogn) sort, using a loop can compare results, but this will mess up the array, the array index will be messy, you need to use a data structure to store the index

The whole process is:

  • Declare a HashMap to store the values and subscripts of the original array
  • Loop through an array to store the data into a HashMap
  • Sort the array
  • Loop array, using a double pointer, the sum of two digits less than target, the front pointer moved backward, the sum of two digits greater than target, the back pointer moved forward, equal, then fetch the corresponding index from the HashMap

Time complexity: O(n + nlogn + n) = O(nlogn)

Space complexity: Because HashMap is used, O(n)

Time complexity is less, like logic is more complex…

Idea 2:

In the double loop, the purpose of the second loop is to find the value of target-self from the array. The loop must be O(n). 👆 uses HashMap above, and the known query complexity of HashMap is O(1)

The whole process is:

  • Declare a HashMap to store the values and subscripts of an array
  • A loop array that looks for a value in the HashMap with a value of target-self. If it does not exist, the current value exists, and if it does, the subscript of the value is extracted from the HashMap

Time complexity: O(n) = O(n)

Space complexity: Because HashMap is used, O(n)

The time complexity is smaller, the logic is much simpler, so let’s try it separately

2.2 Sort + double pointer

class Solution {
    class Test {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        // Cache, you can use List to store elements with the same value, or you can ignore them
        Map<Integer, List<Integer>> cache = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (cache.containsKey(nums[i])) {
                cache.get(nums[i]).add(i);
                continue;
            }
​
            List<Integer> array = new ArrayList<>();
            array.add(i);
            cache.put(nums[i], array);
        }
​
        // use the sorting method provided by the system
        Arrays.sort(nums);
​
        // Double pointer moves before and after
        int head = 0;
        int tail = nums.length - 1;
        while (head < tail) {
            if (nums[head] + nums[tail] == target) {
                int i = cache.get(nums[head]).remove(0);// Prevent the same element
                int j = cache.get(nums[tail]).get(0);
                result[0] = i;
                result[1] = j;
                return result;
            } else if (nums[head] + nums[tail] > target) {
                tail--;
            } else{ head++; }}returnresult; }}Copy the code

Submit the results

Execution time increased from 56ms to 8ms, memory consumption decreased from 38.5MB to 39MB, try a solution

2.3 a HashMap

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        / / cache
        Map<Integer, Integer> cache = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int key = target - nums[i];
            if (cache.containsKey(key)) {
                result[0] = cache.get(key);
                result[1] = i;
                return result;
            }
            cache.put(nums[i], i);
        }
        returnresult; }}Copy the code

Submit the results

If the wrong place please point out, there are other solutions, you can also leave a message, as a novice, also in learning, thank you browse.